B:Similar Arrays

I used the brute force approach, which is slower to implement.

Note that it is even as long as there is 1 even number in the array. It is easier to compute the inverse of the function => i.e., all numbers are odd!

C: Inserting ‘x’

I calcuate the palindrome length and then calcuate how many x should be inserted - WAed because I didn’t consider the case of AXBXXCCXBXXA!!!

Instead, we can just modifly to standard palindrome check slightly, i.e., when we see a mistach at current head and tail, according to the rule, we know exactly the optimal soltuion will be. This will greatly simplify the code.

Expanding on this, what if we can insert any letters, can it be done on O(n)?

Idea 1

Construct t = reverse(s) + $ + s, and then run z-function on t, if i + z[i] == length(t), then we know the substring at i….z[i] is a palindrome suffix of s!

Idea 2

Construct a rolling hash of each suffix/preifx, and compare each (i, n-i-1) pair, this should be close to O(N), as long as our hash function does not have too much collision!