針對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)。