214. Shortest Palindrome

[mah-shamim]

Topics: String, Rolling Hash, String Matching, Hash Function

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.

Example 1:

• Input: s = "aacecaaa"
• Output: "aaacecaaa"

Example 2:

• Input: s = "abcd"
• Output: "dcbabcd"

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of lowercase English letters only.

Footnotes

1. Palindrome A **palindrome** is a string that reads the same forward and backward. ↩

[basharul-siddike]

We need to find the shortest palindrome by adding characters in front of a given string. We can approach this by identifying the longest prefix of the string that is already a palindrome. Once we have that, the remaining part can be reversed and added to the front to make the entire string a palindrome.

Approach:

1. Identify the longest palindromic prefix: We want to find the longest prefix of the string s that is already a palindrome.
2. Reverse the non-palindromic suffix: The part of the string that isn't part of the palindromic prefix is reversed and added to the beginning of the string.
3. Concatenate the reversed suffix and the original string to form the shortest palindrome.

To do this efficiently, we can use string matching techniques such as the KMP (Knuth-Morris-Pratt) algorithm to find the longest palindromic prefix.

Step-by-Step Solution:

1. Create a new string by appending the reverse of the string s to s itself, separated by a special character '#' to avoid overlap between the string and its reverse.

   Let the new string be s + '#' + reverse(s).

2. Use the KMP partial match table (also known as the LPS array, longest prefix suffix) on this new string to determine the longest prefix of s that is also a suffix. This will give us the length of the longest palindromic prefix in s.

3. Construct the shortest palindrome by adding the necessary characters to the front.

Let's implement this solution in PHP: 214. Shortest Palindrome

<?php
/**
* @param String $s
* @return String
*/
function shortestPalindrome($s) {
  // If the string is empty, return an empty string
  if (empty($s)) {
      return $s;
  }

  // Reverse of the string
  $rev_s = strrev($s);

  // Form the new string as s + '#' + reverse(s)
  $combined = $s . '#' . $rev_s;

  // Compute the LPS array for this combined string
  $lps = computeLPS($combined);

  // Length of the longest palindromic prefix in s
  $longest_palindromic_prefix_len = $lps[strlen($combined) - 1];

  // The characters that need to be added to the front are the remaining part of the string
  $remaining = substr($s, $longest_palindromic_prefix_len);

  // Add the reverse of the remaining part to the front of s
  return strrev($remaining) . $s;
}

/**
* Helper function to compute the KMP (LPS array) for string matching
*
* @param $pattern
* @return array
*/
function computeLPS($pattern) {
  $n = strlen($pattern);
  $lps = array_fill(0, $n, 0);
  $len = 0;
  $i = 1;

  while ($i < $n) {
      if ($pattern[$i] == $pattern[$len]) {
          $len++;
          $lps[$i] = $len;
          $i++;
      } else {
          if ($len != 0) {
              $len = $lps[$len - 1];
          } else {
              $lps[$i] = 0;
              $i++;
          }
      }
  }
  return $lps;
}
?>

Explanation:

1. computeLPS Function:

   • This function computes the longest prefix which is also a suffix (LPS) for the given string. This helps to identify how much of the string s is already a palindrome.

2. Forming the Combined String:

   • We combine the original string s with its reverse and separate them by a special character #. The special character ensures that there is no overlap between s and reverse(s).

3. Using the LPS Array:

   • The LPS array tells us the longest prefix in s which is also a suffix of s. This corresponds to the longest part of the string that is already a palindrome.

4. Constructing the Shortest Palindrome:

   • We find the portion of the string that isn't part of the longest palindromic prefix and reverse it. Then, we add the reversed part to the front of the original string s.

Time Complexity:

• The time complexity of this solution is O(n), where n is the length of the string. This is because we are using the KMP algorithm, which runs in linear time.

Example Walkthrough:

Example 1:

Input: s = "aacecaaa"

1. Reverse of s: "aaacecaa"
2. Combined string: "aacecaaa#aaacecaa"
3. LPS array for the combined string gives the longest palindromic prefix as "aacecaaa".

Since the whole string is already a palindrome, no characters need to be added. So the output is "aaacecaaa".

Example 2:

Input: s = "abcd"

1. Reverse of s: "dcba"
2. Combined string: "abcd#dcba"
3. LPS array tells us that the longest palindromic prefix is just "a".

So, we add "dcb" (reverse of "bcd") to the front of s, resulting in "dcbabcd".

Conclusion:

This solution efficiently finds the shortest palindrome by leveraging string matching techniques and the KMP algorithm to identify the longest palindromic prefix. The complexity is linear, making it suitable for large input sizes up to 5 * 10^4.

[mah-shamim]

Thanks to solve the Shortest Palindrome problem

[basharul-siddike]

Thanks