## Monday, December 19, 2016

### Check for Palindrome after every character replacement Query

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