对于Q个查询，将以下内容翻译成中文：在三进制字符串中，需要替换的最小字符数以删除所有回文子字符串

回文字符串是指与其反转字符串相等的字符串。给定一个包含‘0’、‘1’和‘2’的字符串，以及一个长度为N的数组Q，给定数组的每个索引表示一个范围，范围由一对形式的值表示。我们需要找到在给定范围内需要替换的最小字符数，以确保该范围内没有任何回文子字符串。

示例示例

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

Output: 1 1 3

Explanation

的中文翻译为：

解释

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

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

对于范围在5到10之间的数字，我们有回文数020、000和20002。我们可以将第一个2更改为'1'，将下一个索引的'0'更改为'2'，并将倒数第二个索引的值更改为'1'，以去除所有的回文数。

Naive Approach

的中文翻译为：

天真的方法

在这种方法中，思路是获取给定范围的所有组合，并找到没有回文数的组合，所需的最小更改次数。但问题是时间复杂度。

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

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

动态规划

Idea

的中文翻译为：

Idea

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

我们有三个不同的字符，我们需要它们全部来使给定的字符串没有回文。总共有size个选择或序列，我们可以以这样的方式形成序列，即没有回文存在，而这些序列是字符串'012'的排列。

我们将使用dp数组或向量来存储所有可能的情况，每个序列都会给出较少的字符数，我们将使用该序列。

实施

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

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

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

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

Example

的中文翻译为：

示例

#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)。

以上是对于Q个查询，将以下内容翻译成中文：在三进制字符串中，需要替换的最小字符数以删除所有回文子字符串的详细内容。更多信息请关注PHP中文网其他相关文章！