C++ 替换三进制字符串中的最小字符以删除所有回文子串（对于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(QN(3^N))。

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

动态规划

思路

这个问题的思路是，我们不需要在给定范围内有任何回文串，且偶数长度的最小可能回文串长度为2，奇数长度的为3。

我们有三个不同的字符，我们需要它们都出现在给定字符串中才能满足无回文串的要求。总共有size种选择或序列，通过这些序列我们可以形成一种无回文串的序列，这些序列就是字符串’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)。