Hi everyone,

I've been trying to solve the problem JUSTAPAL from SPOJ during the last few days with no success.

My first approach was to do the following algorithm:

ans = 0
for each position i in the string
  len <- length of the longest palindrome centered at i
  len2 <- length of longest palindrome ignoring first pair of mismatched chars at pos (i-len, i+len)
  if (i-len, i+len) have the same pair of chars than (i-len2, i+len2)
    len3 <- length of the longest palindrome also ignoring second pair of mismatched chars at pos (i-len2, i+len2)
    ans = max(ans, len3)  
  else
    fixpos <- pos to swap either i-len or i+len to make them equal
    if fixpos is valid and is farther than len2
      ans = max(ans, len2)
    else if fixpos is valid
      ans = max(ans, abs(fixpos-i+1))
    else
      ans = max(ans, len)

So this is the main idea and with a few changes I'm doing it for both odd and even cases. I'm using O(nlogn) Suffix Array + LCP with Sparse Table so the overall complexity of the algorithm is O(nlogn). Which is giving me TLE :(

Now I'm thinking about some way of doing it in O(n) by using some two pointers + hashing approach like the following algorithm:

ans = 0
for each position i in the string
  while hash[i-ans+1...i+ans-1] == rev_hash[i-ans+1...i+ans-1]
    ans += 1
  if number of odd items not including the center is 2
    fixpos <- pos to swap either i-ans or i+ans to make them equal
    while (hash[i-ans+1...i+ans-1] == rev_hash[i-ans+1...i+ans-1] + (changes in hash made by swap)
          and fixpos is out of these bounds)
      ans += 1

So this approach is O(n) as we are only entering the inner loops when the ans can be increased. However there are two problems with this approach:

• It's horrible to implement D: ... but maybe that's just me (:
• There's a case in which all chars have even parity (not counting the center) but they are not the same. However there exist some swap inside the palindrome that makes them the same (similar to the len3 case in the previous approach).

I'm trying to figure out how can I approach this all even case in which I guess I don't need to know which chars to change but if there's only one swap necessary or something like that.

Can you please help me with some ideas + insights about this?

Also, if any of you have a better approach or if my idea is wrong please let me know :D

Thanks!