[Math] Check if we can turn a string into a palindrome by reversing a substring

Question

Given a string consisting of lower-case characters from English alphabets, we want to reverse a substring from the string such that the string becomes a palindrome.

Note : A Palindrome is a string which equals its reverse.

We need to tell if some substring exists which could be reversed to convert the string into palindrome.

Example : Let string be "zakdakdz". Then the answer for this string is "yes", since we can reverse the string between indexes 4 and 6 to get zakddkaz

Basic Approach : Try to reverse each and every substring and check if we get palindrome or not. However, this is bad approach for a long string.

So is there a better way to solve it ?

Answer 1

Quick heuristic: For very large strings, we can count the frequency of all letters ("a", "b", ...) to quickly weed out strings that cannot possibly be turned into a palindrome.

Let $n$ be the length of the string $S$.

If $n$ is even, then each letter must occur an even number of times. If $n$ is odd, then the same is true except for exactly one letter.

Search for solutions: Let $S_i$ be the i-th letter of $S$ and $S_{a:b}$ the substring from (inclusive) index $a$ to $b$.

Checking a substring $S_{a:b}$:

• Is $S_a = S_b$? If yes, check $S_{a+1:b-1}$ instead.
  • Special case: If this substring has a length of 0 or 1, then $S$ is already a palindrome.
• Search for all $S_a$ and $S_b$ in $S_{a+1:b-1}$. If there are none, return false.
• Foreach $S_a \in S_{a+1:b-1}$ at index $i$:
  • Reverse the substring $S_{i:b}$.
  • Is $S$ now a palindrome? If yes, return true.
• Foreach $S_b \in S_{a+1:b-1}$ at index $j$:
  • Reverse the substring $S_{a:j}$.
  • Is $S$ now a palindrome? If yes, return true.
• Return false.

Now apply the substring algorithm to $S$ as $S_{1:n}$.