Hi everyone,↵
↵
I've been trying to solve the problem [JUSTAPAL](https://www.spoj.com/problems/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! ↵
↵
↵
I've been trying to solve the problem [JUSTAPAL](https://www.spoj.com/problems/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! ↵
↵
