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:

1. Read the string
2. Extract the substring for each query Q, from L to R
3. Response whether the substring forms palindrome if you have chance to rearrange them. If “yes”, return
4. 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