For Q queries, translate the following into Chinese: In a ternary string, the minimum number of characters that need to be replaced to remove all palindromic substrings

A palindrome string is a string that is equal to its reversed string. Given a string containing '0', '1' and '2', and an array Q of length N, each index of the given array represents a range, and the range is represented by a pair of values ​​of the form. We need to find the minimum number of characters that need to be replaced in a given range to ensure there aren't any palindromic substrings in the range.

ExampleExample

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

Output: 1 1 3

The Chinese translation of

Explanation

is:

Explanation

For the range 0 to 4, we have two palindromes 010 and 1001, we can change the index 2 to '2', so that there will be no palindromes left.

For the range 2 to 5, we only have one palindrome number which is 010, which can be changed by changing the first zero to 2.

For numbers in the range 5 to 10, we have the palindrome numbers 020, 000 and 20002. We can change the first 2 to '1', the next index's '0' to '2', and the second to last index's value to '1' to get rid of all the palindromes.

The Chinese translation of

Naive Approach

is:

Naive Approach

In this method, the idea is to get all combinations of a given range and find the minimum number of changes required for a combination without palindromes. But the problem is time complexity.

To implement this method, we must make a recursive call and traverse the string. At each index, we have three choices, making the time complexity of getting all strings 3^N. Now, we have to answer Q queries, and for each case we have to check whether removing the palindrome string makes the time complexity O(Q*N*(3^N)).

For recursive calls, we have to maintain space of N, which means the space complexity is O(N).

Dynamic Planning

The Chinese translation of

Idea

is:

Idea

The idea of ​​​​this question is that we do not need to find any palindrome number in a given range. The minimum possible palindrome number length is 2 for even numbers and 3 for odd numbers.

We have three different characters and we need them all to make the given string without palindromes. There are total size choices or sequences, we can form the sequences in such a way that no palindromes exist and these sequences are permutations of the string '012'.

We will use dp array or vector to store all possible cases, each sequence will give less number of characters and we will use that sequence.

Implementation

In the implementation part, first, we will create a function that will accept a string, sequence, DP vector and number of sequences as parameters and update the DP vector.

In this function, first, we will update the value of the first index, then for each unmatched case, we will update the value of the current index of the DP vector.

We will create another function in which we will manually enter all possible sequences and store them in an array and create a DP vector.

We will call the above function by passing the value for preprocessing, and then answer each query by iterating through it one by one.

The Chinese translation of

Example

is:

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;
}

Output

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

Time and space complexity

The time complexity of the above code is O(N Q), where N is the number of characters in the string and Q is the number of queries.

The space complexity of the above code is O(N) because we store the state in a vector of size N.

in conclusion

In this tutorial, we implemented a piece of code to find out the minimum number of characters that need to be changed when doing some queries in a given range so as not to leave a palindrome string. We implemented this code using the concepts of dynamic programming with time complexity of O(N Q) and space complexity of O(N).

The above is the detailed content of For Q queries, translate the following into Chinese: In a ternary string, the minimum number of characters that need to be replaced to remove all palindromic substrings. For more information, please follow other related articles on the PHP Chinese website!