Shortest Palindrome

In this approach, we will find the largest palindromic substring of ‘STR’ from the beginning, and we will reverse the remaining substring of ‘STR’ and append it to the beginning of ‘STR’.

5454545

Let’s write ‘STR’ as ‘PSTR’ + ‘RSTR’, where ‘PSTR’ is the palindromic substring of ‘STR’ and ‘RSTR’ is the remaining substring of ‘STR’. Then our answer would be REVERSE(‘RSTR’) + ‘STR’.5454545
 

Algorithm:

• Initialize a variable 'REV' to store the reverse of 'STR'.
• Initialize a variable 'N' to store the length of 'STR'.
• Iterate 'I' in 0 to 'N':
  • If the substring of 'REV' from index 'I' is equal to the substring of 'STR' up to index 'I':
    • Return the substring of 'REV' up to index 'I' append with 'STR'.
• Return empty character if the palindrome cannot be formed.

In approach 1, we found the largest palindromic substring of ‘STR’ from the beginning using string comparison, which takes O(N) time. In this approach, we will look at a more efficient to find the largest palindromic substring by reducing the size of the string to search for the substring without checking the complete substring each time.
 

To reduce the size of the string to be searched, we use two pointers, ‘L’ and ‘R’. Initially, we will et ‘L’ as 0 and iterate ‘R’ from ‘N’ - 1 to 0. We will increment ‘L’ by 1 whenever STR[L] equals ‘STR[R]. Now, the substring of ‘STR’ from index 0 to ‘L’ must contain the largest palindromic substring.
 

Algorithm:

• newBase case. If 'STR' is null or the length of 'STR' is less than or equal to 1:
  • Return 'STR'.
• Initialize a variable 'N' to store the length of 'STR'.
• Initialize a variable 'L'. 'L' is the left pointer.
• Iterate 'R' in 'N' - 1 to 0. Here 'R' is the right pointer.
  • If the character at index 'L' is equal to the character at index 'R':
    • Increment left pointer by 1.
• If 'L' is equal to 'N':
  • Return 'STR'.
• Initialize a variable 'SUFFIX' to store substring of 'STR' from index 'L' to the end.
• Initialize a variable 'PREFIX' to store reverse of 'SUFFIX'.
• Add 'PREFIX' in front and 'SUFFIX' at end of 'FINDSHORTESTPALINDROME(STR.SUBSTRING(0, L))' and return it.

Prerequisite: KMP algorithm for string matching.
 

In approach 1, we saw that if we write ‘STR’ as ‘PSTR’ + ‘RSTR’, where ‘PSTR’ is the palindromic substring of ‘STR’ and ‘RSTR’ is the remaining substring of ‘STR’. Then our answer would be REVERSE(‘RSTR’) + ‘STR’.
 

Now define a string ‘KSTR’ =‘STR’ + # + REVERSE(‘STR’) = (‘PSTR’ + ‘RSTR’) + # + (REVERSE(‘RSTR’) + ‘PSTR’). Now, we can run KMP on ‘KSTR’ to find the longest prefix, which is also a suffix that will be ‘PSTR’.

Once we know ‘PSTR’ then we can easily find ‘RSTR’. Then our answer will be REVERSE(‘RSTR’) + ‘STR’.
 

For example, if ‘STR’ is “abac”, then ‘KSTR’ will be “abacd#dcaba”. Now. We can see that “aba” is the longest prefix which is also a suffix. So:

‘PSTR’ -> “aba”.

‘RSTR’ -> “cd”

REVERSE(‘RSTR’) -> “dc”.

Answer -> REVERSE(‘RSTR’) + ‘STR’ = “dc” + “aba” = “dcaba”.
 

To find the longest prefix, which is also a suffix, we will use KMP. We will define a table ‘TABLE’  that will store the index of the character, which will be compared with the next character if the current character is the same as the prefix’s last character. If a match is found, we will increment the length of the previous substring solution, i.e., we will set ‘TABLE[I]’(‘I’ is the index) as ‘TABLE[I - 1]’ + 1. Otherwise, we will shorten the match string length and jump to the prefix part that we used to match suffix ended at ‘I’ - 1. Then, in the end, the value of the last element of ‘TABLE,’ i.e., TABLE[TABLE.LENGTH - 1] will represent the longest common prefix's last index which we will use to find the longest common prefix.
 

Algorithm:

• Initialize a string 'TEMP' which is equal to 'STR' + # + REVERSE('STR').
• Initialize an integer array ‘TABLE’ to store the match result of prefix and suffix.
• Return REVERSE(STR.SUBSTRING(TABLE[TABLE.LENGTH - 1])) + ‘STR’.

Maintain a function ‘GETTABLE(string STR)’:

• Initialize an integer array ‘TABLE’.
• Initialize a variable ’INDEX’ that will point to matched char in the prefix part.
• Iterate 'I' in 1 to STR.LENGTH:
• If the character at index ‘INDEX’ is equal to the character at index ‘I’:
  • Set ‘TABLE[I]’ as ‘TABLE[i-1] + 1.
  • Increment ‘INDEX’ by 1.
• Otherwise:
  • Set ‘INDEX’ as ‘TABLE[I - 1]’.
  • While ‘INDEX’ is greater than 0 and character at index ‘INDEX’ is not equal to the character at index ‘I’:
    • Set ‘INDEX’ as ‘TABLE[INDEX - 1].
  • If the character at index ‘INDEX’ is equal to the character at index ‘I’:
    • Increment ‘INDEX’ by 1.
  • Set ‘TABLE[I]’ as ‘INDEX’.
• Return ‘TABLE’.