http://www.geeksforgeeks.org/check-for-palindrome-after-every-character-replacement-query
Given a string str and Q queries. Each query contains a pair of integers (i1, i2) and a character ‘ch’. We need to replace characters at indexes i1 and i2 with new character ‘ch’ and then tell if string str is palindrome or not. (0 <= i1, i2 < string_length) Examples:
An efficient solution is to use hashing. We create an empty hash set that stores indexes that are unequal in palindrome (Note: ” we have to store indexes only first half of string that are unequal “).
Given string "str" and length 'n'.
Create an empty set S and store unequal indexes in first half.
Do following for each query :
1. First replace character at indexes i1 & i2 with
new char "ch"
2. If i1 and/or i2 are/is greater than n/2 then convert
into first half index(es)
3. In this step we make sure that S contains maintains
unequal indexes of first half.
a) If str[i1] == str [n - 1 - i1] means i1 becomes
equal after replacement, remove it from S (if present)
Else add i1 to S
b) Repeat step a) for i2 (replace i1 with i2)
4. If S is empty then string is palindrome else NOT
Time Complexity : O(Q + n)
// This function makes sure that set S contains// unequal characters from first half. This is called// for every character.void addRemoveUnequal(string &str, int index, int n, unordered_set<int> &S){ // If character becomes equal after query if (str[index] == str[n-1-index]) { // Remove the current index from set if it // is present auto it = S.find(index); if (it != S.end()) S.erase(it) ; } // If not equal after query, insert it into set else S.insert(index);}// Takes two inputs for Q queries. For every query, it// prints Yes if string becomes palindrome and No if not.void Query(string &str, int Q){ int n = str.length(); // create an empty set that store indexes of // unequal location in palindrome unordered_set<int> S; // we store indexes that are unequal in palindrome // traverse only first half of string for (int i=0; i<n/2; i++) if (str[i] != str[n-1-i]) S.insert(i); // traversal the query for (int q=1; q<=Q; q++) { // query 1: i1 = 3, i2 = 0, ch = 'e' // query 2: i1 = 0, i2 = 2, ch = 's' int i1, i2; char ch; cin >> i1 >> i2 >> ch; // Replace characters at indexes i1 & i2 with // new char 'ch' str[i1] = str [i2] = ch; // If i1 and/or i2 greater than n/2 // then convert into first half index if (i1 > n/2) i1 = n- 1 -i1; if (i2 > n/2) i2 = n -1 - i2; // call addRemoveUnequal function to insert and remove // unequal indexes addRemoveUnequal(str, i1 , n, S ); addRemoveUnequal(str, i2 , n, S ); // if set is not empty then string is not palindrome S.empty()? cout << "YES\n" : cout << "NO\n"; }}
Time complexity O(Q*n) (n is length of string )
bool IsPalindrome(string &str){ int n = strlen(str); for (int i = 0; i < n/2 ; i++) if (str[i] != str[n-1-i]) return false; return true;}// Takes two inputs for Q queries. For every query, it// prints Yes if string becomes palindrome and No if not.void Query(string &str, int Q){ int i1, i2; char ch; // Process all queries one by one for (int q = 1 ; q <= Q ; q++ ) { cin >> i1 >> i2 >> ch; // query 1: i1 = 3 ,i2 = 0, ch = 'e' // query 2: i1 = 0 ,i2 = 2 , ch = 's' // replace character at index i1 & i2 with new 'ch' str[i1] = str[i2] = ch; // check string is palindrome or not (isPalindrome(str)== true) ? cout << "YES" << endl : cout << "NO" << endl; }}