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.
Example 1:
Input: s = "aacecaaa"
Output: "aaacecaaa"
Example 2:
Input: s = "abcd"
Output: "dcbabcd"
Constraints:
- 0 <= s.length <= 5 * 104
sconsists of lowercase English letters only.
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The problem asks us to create the shortest palindrome by adding characters to the front of a string. A simple brute force way to create a palindrome is to repeatedly check each prefix of the string and find out if it forms a palindrome extending towards the rest of the string. If not, we keep adding the minimum necessary characters at the front, checking each time if the result is a palindrome.
Approach:
- Start by reversing the given string
sto getrev_s. - If
sitself is a palindrome, return it. - Otherwise, iterate through each index
iof the strings: - Form a string with
rev_s.substring(0, i)appended to the front of the originals. - Check if this new string is a palindrome.
- If it is, it means
s.substring(i)is the largest palindromic prefix. - Continue this until a palindrome is formed.
Code:
- Time Complexity: O(n^2). Each substring comparison takes O(n) time and there are n such attempts.
- Space Complexity: O(n). For storing the reversed string and additional substring storage.
2. KMP Algorithm
Intuition:
To reduce the time complexity, we can use the Knuth-Morris-Pratt algorithm (KMP) prefix function. The idea is to find the greatest palindrome prefix in the string using the prefix and suffix match pattern from the reversed string. This helps us quickly determine which part of the string needs to be mirrored from the end.
Approach:
- Concatenate the string
swith#and its reversed versionrev_sto create a new stringconcat. - The
#is a delimiter ensuring we don't accidentally match acrosssandrev_s. - Compute the KMP table (longest prefix that is also a suffix) for this concatenated string.
- The value at the last index of the KMP table will tell how many characters from the start of
sform a valid palindrome. - The rest of the characters of
scan be added in reverse at the beginning to form the shortest palindrome.
Code:
- Time Complexity: O(n). The KMP algorithm runs in linear time relative to the length of the concatenated string.
- Space Complexity: O(n). Space used for the KMP table and additional reversed string.