- Dynamic Programming, prefix, Strings, TrueGeek, TrueGeek-2021

Minimum characters to be replaced in Ternary string to remove all palindromic substrings for Q queries

  #include #define SIZE 100005using namespace std;  void preprocess(string& s, string& t,                int prefix[][SIZE],                int n, int i){        prefix[i][0] = (s[0] != t[0]);      for (int j = 1; j < n; j++) {                                  prefix[i][j]            = prefix[i][j - 1]              + (s[j] != t[j % 3]);    }    return;}  void minChangesNonPalindrome(    string str, int N, int Q,    vector queries){          int prefix[6][SIZE];                  vector sequences        = { "012", "021", "102",            "120", "201", "210" };      for (int i = 0; i < 6; i++) {                          preprocess(str, sequences[i],                   prefix, N, i);    }          for (int i = 0; i < Q; i++) {          int l = queries[i].first + 1,            r = queries[i].second + 1;        int cost = INT_MAX;                                  for (int j = 0; j < 6; j++) {                          cost                = min(                    cost,                    prefix[j][r]                        - prefix[j][l]                        + (str[l] != sequences[j][l % 3]));        }        cout