针对Q个查询，将三元字符串中需要替换的最小字符数，以移除所有回文子字符串

---

回文串是指等于其反转字符串的字符串。给定一个包含‘0’、‘1’和‘2’的字符串和一个长度为N的数组Q，数组的每个索引都表示一个范围（以对的形式）。我们必须找到在给定范围内需要替换的最小字符数，以使该范围内不再存在任何回文子字符串。

示例

Input1: string s: “01001020002”, int Q = {{0,4}, {2,5}, {5,10}};

Output: 1 1 3

解释

对于范围0到4，我们有两个回文串010和1001，我们可以将索引2改为‘2’，这样就不会剩下任何回文串。

对于范围2到5，我们只有一个回文串010，可以通过将第一个零改为2来改变。

对于范围5到10，我们有回文串020、000和20002。我们可以将第一个2改为‘1’，下一个索引‘0’改为‘2’，并将倒数第二个索引值改为‘1’，以移除所有回文串。

朴素方法

在这种方法中，其思想是更改给定范围的所有组合，并找到一个不需要回文且所需更改最少的组合。但问题在于时间复杂度。

为了实现这种方法，我们必须执行递归调用并遍历字符串。在每个索引处，我们有三个选择，这使得仅仅获取所有字符串的时间复杂度为3^N。现在，我们必须回答Q个查询，并且对于每种情况，我们都必须检查回文串的移除，这使得时间复杂度为O(Q*N*(3^N))。

对于递归调用，我们必须维护N的空间，这意味着空间复杂度为O(N)。

动态规划

思想

这个问题背后的思想是，我们不需要在给定范围内有任何回文，最小的回文长度为2（偶数长度）和3（奇数长度）。

我们有三个不同的字符，我们需要全部使用它们来使给定的字符串无回文。共有大小选择或序列，我们可以通过这些选择或序列来形成序列，这样就不会存在回文，而这些序列就是字符串‘012’的排列。

我们将创建一个dp数组或向量来存储所有可能的案例以及每个序列，我们将使用字符数较少的序列。

实现

在实现部分，首先，我们将创建一个函数，该函数将字符串、序列、DP向量和序列数作为参数，并将更新DP向量。

在这个函数中，首先，我们将更新第一个索引的值，然后对于每个错配，我们将更新DP向量的当前索引的值。

我们将创建另一个函数，在这个函数中，我们将手动输入所有可能的序列并将它们存储在数组中，并将创建一个DP向量。

我们将调用上述函数进行预处理，传递值，然后逐一回答每个查询。

示例

#include <bits/stdc++.h>
#define SIZE 100005
using namespace std;
// function to get the pre-processing of the results 
void preprocess(string& str, string& seq, vector<vector<int>>&dp, int n, int i){
   dp[i][0] = (str[0] != seq[0]); // initialzie dp vector 
   for (int j = 1; j < n; j++) {
   
      // storing the results if matched then adding zero otherwise one
      dp[i][j] = dp[i][j - 1] + (str[j] != seq[j % 3]);
   }
   return;
}

// function to find the number of changes required for each query 
void changesReq(string str, vector<pair<int, int>> Q){
   int len = str.length(); // size of the given string 
   int q = Q.size(); // number of queries 
   vector<vector<int>>dp(6,vector<int>(len)); // dp vector to store the states results 
   
   // vector to store each possible non-palindromic sequency 
   vector<string> seq= { "012", "021", "102", "120", "201", "210" };
   for (int i = 0; i < 6; i++){
   
      // for each sequence storing state results in vector 
      preprocess(str, seq[i], dp, len, i);
   }	
   
   // getting all the queries 
   for (int i = 0; i < q; i++){
      int l = Q[i].first;
      int	r = Q[i].second;
      int ans = INT_MAX;
      
      // finding the minimum cost amount 
      for (int j = 0; j < 6; j++) {
         // Find the cost
         ans = min(ans, dp[j][r] - dp[j][l] + (str[l] != seq[j][l%3]));
      }
      cout <<ans<<"  ";
   }
}
int main(){
   string str = "01001020002";
   vector<pair<int, int>>Q = {{0,4}, {2,5}, {5,10}};
   
   // calling the function 
   cout<<"The minimum characters to be replaced in the Ternary string to remove all palindromic substrings for Q queries is "<<endl;
   changesReq(str, Q);
   return 0;
}

输出

The minimum characters to be replaced in the Ternary string to remove all palindromic substrings for Q queries is 
1  1  3  

时间和空间复杂度

上述代码的时间复杂度为O(N + Q)，其中N是字符串中字符的个数，Q是查询的个数。

上述代码的空间复杂度为O(N)，因为我们将状态存储在大小为N的向量中。

结论

在本教程中，我们实现了一个代码，用于查找在给定范围内针对某些查询需要更改的最小字符数，以使没有回文串剩余。我们使用动态规划的概念实现了该代码，时间复杂度为O(N+Q)，空间复杂度为O(N)。