Palindrome string is one of the problems always presents in Interview or Competitive Programming. Google Kick Start has launched there practice session in four days, included `Building Palindromes`

.

# The Problem

To avoid rambling, the problem is shortened and paraphrased to keep the core problem only. If you wish to do it yourself, please access here

```
A palindrome is a string that is the same written forwards and backwards. For example, ANNA, RACECAR, AAA and X are all palindromes, while AB, FROG and YOYO are not.
Given Q questions, the i-th question is: can we form a inclusive substring to palindrome started at L to R? We may rearrange the string to make it palindrome if necessary, and if it coule be, answer "yes". In the end, count number of these "yes"(s).
Be noticed that L, R is human natural count, which means started at 1, not 0 like computer.
Limits
Time limit: 30 seconds.
Memory limit: 1 GB.
1≤T≤100.
1≤Li≤Ri≤N.
Test Set 1
1≤N≤20.
1≤Q≤20.
Test Set 2
1≤N≤100000.
1≤Q≤100000.
```

```
Explanation
In Sample Case #1, N = 7 and Q = 5.
- For the first question, substring `AACC` => Rearrange to palindrome ACCA (or CAAC).
- For the second question, substring `A`. This is already a palindrome
- For the third question, `BAAC` => This cannot be rearranged into a palindrome.
- For the fourth question, `CA` => This cannot be rearranged into a palindrome.
- For the fifth question, `AACCA` => Rearrange to form the palindrome ACACA (or CAAAC).
- In total, answer "yes" to 3
In Sample Case #2, N = 3 and Q = 5. For the first question, `XYZ` to create a palindrome. This is impossible, and since the rest are the same as the first one, the answer is 0.
```

# Naive Solution

The problem should handle 4 phases:

- Read the string
- Extract the substring for each query Q, from L to R
- Response whether the substring forms palindrome if you have chance to rearrange them. If “yes”, return
- Count these “yes”

So the core is in step 3, response it as fast as possible. In this Naive Solution, since we just have to answer yes or no without process rearrange, one possible solution is to keep each character in `Dictionary`

represents as frequency of itself. Acknowledged from characteristics of palindrome string is only `one/no one odd frequency`

and the rest should have `empty or even frequency`

The code below reveals 2 steps: first to accumulate frequency and second to check odd value `val % 2 == 1`

, if odd goes more than 1 time then quickly return `False`

```
def query(text, L, R):
dct = {}
for c in text[L-1: R]:
if c in dct:
dct[c] += 1
else:
dct[c] = 1
is_odd_first_time = False
for val in dct.values():
if val % 2 == 1:
if is_odd_first_time:
return False
is_odd_first_time = True
return True
def test():
N, Q = map(int, input().split())
text = input()
sayYes = 0
for _ in range(Q):
L, R = map(int, input().split())
sayYes += query(text, L, R)
return sayYes
```

The problem of this Naive Solution is we need to create every of Dictionary for each query Q => Time and Space Complexity = O(Q*(R-L))

You definetely cannot pass through Test Set 2 (Time Limit Exceeded)

# Prefix XOR

Exclusive XOR compares the bits of two numbers, in which the result bits are set to 1 if input bits are different and set to 0 if the inputs are the same

For the string `AABC`

Consider decoding character into array whose unique value `['A', 'B', 'C']`

.

```
decode('A') = [1, 0, 0]
decode('B') = [0, 1, 0]
decode('C') = [0, 0, 1]
```

Then declare `prefix_arr`

as:

```
prefix_arr[0] = decode('A') = [1, 0, 0]
prefix_arr[1] = prefix_arr[0] XOR decode('A') = [1, 0, 0] ^ [1, 0, 0] = [0, 0, 0]
prefix_arr[2] = prefix_arr[1] XOR decode('B') = [0, 0, 0] ^ [0, 1, 0] = [0, 1, 0]
prefix_arr[3] = prefix_arr[2] XOR decode('C') = [0, 1, 0] ^ [0, 0, 1] = [0, 1, 1]
```

Observe from result

```
prefix_arr[0] = [1, 0, 0] => 'A' => Palindrome
prefix_arr[1] = [0, 0, 0] => 'AA' => Palindrome
prefix_arr[2] = [0, 1, 0] => 'AAB' => can arrange to 'ABA' => Palindrome
prefix_arr[3] = [0, 1, 1] => 'AABC' => Not Palindrome
Inclusive
'AB' = prefix[2] - prefix[0] = [0, 1, 0] - [1, 0, 0] = [-1, 1, 0] => absolute to [1, 1, 0] => Not Palindrome
Second 'A' = prefix[2] - prefox[1] = [0, 1, 0] - [0, 0, 0] = [0, 1, 0] => Palindrome
'ABC' = prefix[3] - prefix[1] = [0, 1, 1] - [0, 0, 0] = [0, 1, 1] => Not Palindrome
```

As you can see, it is true that sum of `1`

and `absoluate(-1)`

is less than or equal 1 brings Palindrome and greater than 1 brings Not Palindrome. There explains that the `even frequency`

return 0 and only keep it final `odd frequency`

, thank to XOR operator

```
def query_v2(arr, L, R):
odd=sum((x-y) % 2 != 0 for x,y in zip(arr[L-1], arr[R]))
return odd <= 1
def test_v2():
N, Q = map(int, input().split())
text = input()
arr = [[0 for _ in range(26)]]
for el in text:
new = arr[-1][::]
new[ord(el)-ord('A')] ^= 1
arr.append(new)
sayYes = 0
for _ in range(Q):
L, R = map(int, input().split())
sayYes += query_v2(arr, L, R)
return sayYes
```

The above code shows I have encoded to 26 places, stored in `arr`

stands for prefix array. After that generated ASCII code via `ord()`

function and put them in exact position. More, instead of XOR entire 2 arrays between last prefix array and decoded char, I can easily address to the prefix array in representative position, then doing XOR with 1 in this line `new[ord(el)-ord('A')] ^= 1`

.

It can submit to pass Test Set 2 now.

Some small optimizations here`(x-y) % 2 != 0`

is based on prefix sum sense, as in this case we could change to `x ^ y`

without changing meaning and result basically. So the code would be as following

```
def query_v2(arr, L, R):
odd=sum((x^y) for x,y in zip(arr[L-1], arr[R]))
return odd <= 1
```

# Further optimization

In this version, I am going to optimize the technique used on previous section, which is array, instead of places the array of 26 places (A to Z), I will place in an array but in bit, known as integer. Ex.`[1, 0, 0]`

would be bits `100`

equivalent to integer of 6

To adjust XOR on specified bit, we will shift 1 into there desired index as usual.

```
def query_v3(arr, L, R):
odd = bin(arr[L-1] ^ arr[R]).count('1')
return odd <= 1
def test_v3():
N, Q = map(int, input().split())
text = input()
arr = [0]
for el in text:
new = arr[-1]
new ^= 1 << ord(el)-ord('A')
arr.append(new)
sayYes = 0
for _ in range(Q):
L, R = map(int, input().split())
sayYes += query_v3(arr, L, R)
return sayYes
```

Some minor optimizations you can consider

If you are using Python 3.10, the count code would be 6 times faster

`int.bit_count()`

Or you could take while loop until it exceeds 1 => return False

# Further expanding problem

During searching for optimized solution, I have found the similar challenge on leetcode.

The problem is expanded to opt for `k`

times replacement on substring, say `ABC`

, you will have at least 1 time to replace `C`

to `A`

, form `ABA`

. Realistically, `ABC`

stands for `[1, 1, 1]`

and sum of 1s is 3. We would like to make valid Palindrome so there becomes `3 div 2 = 1`

=> 1 is the minimum of replacement.

- Another example, say
`ABACDC`

=>`[0, 1, 0, 1]`

=>`2 div 2 = 1`

. Exactly for rearrangement like`CCABDACC`

=>`D`

to`B`

or vice versa =>`CCABBACC`

`AA`

=>`[0]`

=>`0 div 2 = 0`

`AAA`

=>`[1]`

=>`1 div 2 = 0`

```
def query_v4(arr, L, R, k):
odd = bin(arr[L-1] ^ arr[R]).count('1')
return odd // 2 <= k
```

It is done now, time to eat