Leetcode Daily Question 20/09/2024 - 214. Shortest Palindrome

Problem Description:

You are given a string s. You can convert s to a palindrome by adding characters in front of it. Return the shortest palindrome you can find by performing this transformation.

class Solution:
  def shortestPalindrome(self, s: str) -> str:
    indicator = 0
    n = len(s)
    for i in range(n - 1, -1 ,-1):
      if s[indicator] == s[i]:
        indicator += 1
    
    if indicator == n:
      return s
    
    return s[indicator:][::-1] + self.shortestPalindrome(s[:indicator]) + s[indicator:]

Explanation:

We can do this recursively by using a two pointer technique.

We keep track of a left indicating pointer, indicator, and iterate through current string from the right.

When we reach a match we move the indicator forward. At the end, if the indicator reach the length of the string, then we know the string is a palindrome and there is nothing else we need to prepend.

Else, the indicator shows that the longest proper prefix must side somewhere between [0:indicator).

We can see this in the following examples.

Example 1 s = "acecaa" 
indicator = 0, i = 5
s[indicator] == s[5] => indicator = 1;
indicator = 1, i = 4
s[indicator] != s[4] => indicator = 1;
indicator = 1, i = 3
s[indicator] == s[3] => indicator = 2;
indicator = 2, i = 2
s[indicator] == s[2] => indicator = 3;
indicator = 3, i = 1
s[indicator] == s[1] => indicator = 4;
indicator = 4, i = 0
s[indicator] == s[0] => indicator = 5;

Here we see that the longest proper palindromic prefix 
is "aceca" which is actually s[:5], which makes the problem much easier.

However, consider
Example 2 s = "adcba"
s[indicator] == s[5] => indicator = 1;
s[indicator] != s[4] => indicator = 1;
s[indicator] != s[3] => indicator = 1;
s[indicator] != s[2] => indicator = 1;
s[indicator] == s[1] => indicator = 2;
s[indicator] != s[0] => indicator = 2

Here the longest proper palindromic prefix is "a" which is in [0,2) but not exactly s[:2].

We continue doing this until we have constructed the shortest palindrome

def shortestPalindrome(s):
  indicator = 0
  n = len(s) 
  for i in range(n - 1, -1, -1):
    if s[indicator] == s[i]:
      indicator += 1
  if indicator == n:
    return s
  return s[indicator:][::-1] + shortestPalindrome(s[:indicator]) + s[indicator:]

The time complexity is O(n). This is because the worst case is when the longest proper palindromic prefix is 1, the indicator will reach far into the string and the problem only shortened by 2 everytime.

The space complexity is O(1). We do not store any extra data structures.

The full solution can be found near the top of the page.