The shortest palindrome problem in Python

Key takeaways:
The goal is to convert the given string s into the shortest palindrome by adding characters only to the beginning of the string.
Brute force adds the necessary characters in reverse to form the shortest palindrome.
The Knuth-Morris-Pratt (KMP) algorithm enables finding the longest palindromic prefix in linear time $O(n)$ .
Concatenating the string with its reverse and a delimiter in KMP approach helps identify the palindrome efficiently.
The KMP prefix array reveals the longest palindromic prefix in the string.

The shortest palindrome problem is a popular coding challenge often discussed in technical interviews. The task is to transform a given string, s, into its shortest palindrome by adding characters to the beginning.

Problem statement

Given a string s, convert it into the shortest palindrome by adding characters at the start.

Example:

Input: aacecaaa

Output: aaacecaaa

Approach 1: Brute force

The brute force approach solves the problem by identifying the longest palindromic prefix in the string and then adding the missing characters to the start to make it a palindrome.

Let’s walk through the steps of the brute force solution:

Start by reversing the input string s to obtain rev_s.
Example:
If s = "aacecaaa", then rev_s = "aaacecaa".
The next step is to check for the longest palindromic prefix in rev_s that matches the beginning of s. This is done by iterating through the characters of s and rev_s and checking which prefix forms a palindrome.
Example:
For s = "aacecaaa", the longest palindromic prefix in rev_s = "aaacecaa" is "aacecaa".
After identifying the longest palindromic prefix, we add the characters from rev_s that are not part of the palindrome to the beginning of s.
Example:
The non-palindromic portion of rev_s is "a". Add this to the start of s to get the result:
Result: "aaacecaaa".

Let’s look at the following illustration to get a better understanding of the approach:

def shortest_palindrome_bruteforce(s):
    n = len(s)
    s_rev = s[::-1]
    for i in range(n, 0, -1):
        if s[:i] == s_rev[-i:]:
            return s_rev[:n-i] + s
    return ""  # If s has no palindrome substring at all.
test_cases = [
    "aacecaaa",   # Expected: "aaacecaaa"
    "abcd",       # Expected: "dcbabcd"
    "racecar",    # Expected: "racecar"
    "a"          # Expected: "a"
]
for test in test_cases:
    print(f"Input: {test} -> Shortest Palindrome: {shortest_palindrome_bruteforce(test)}")

Time and space complexity

The time complexity of this approach is $O(n^2)$ , where $n$ is the length of the input string. This is because, in the worst case, the function checks each prefix and verifies if it’s a palindrome by reversing it.
The space complexity is linear $O(n)$ as it uses additional space to store the reversed string version.

Note: This approach works but isn’t the most efficient in terms of time and space complexity.

Approach 2: Knuth-Morris-Pratt (KMP) algorithm

The Knuth-Morris-Pratt (KMP) algorithm is famous for pattern searching. The approach is much more efficient than the brute force method and works in linear time. But how does it relate to our problem?

Imagine concatenating the string s and its reverse with a delimiter: s + "#" + rev_s. The problem now is to find the palindrome substring which spans the entire length of s. Using the KMP algorithm, we can compute a prefix array of this concatenated string, which will help us find the desired palindrome substring.

Let’s walk through the steps of this approach:

The first step is to concatenate the original string s with a special delimiter (e.g., #) and its reversed version s[::-1]. This ensures that we can easily compute the longest palindromic prefix. The delimiter ensures no overlap between the original string and its reverse when calculating the prefix array. For example: If s = "aacecaaa", the concatenated string will be: "aacecaaa#aaacecaa"
Next, we compute the prefix array for the concatenated string using the KMP algorithm. The prefix array stores the lengths of the longest proper prefix that is also a suffix for each substring in the concatenated string.
1. We initialize the prefix array with zeros, and use two pointers i (which iterates over the concatenated string) and j(which tracks the length of the longest matching prefix).
2. If characters at positions i and j match, we extend the match by incrementing j. Otherwise, we use the previously computed prefix values to find a shorter matching prefix and adjust j.
The last value in the prefix array (prefix[-1]) gives the length of the longest palindromic prefix in the original string s.
To form the shortest palindrome, we need to add the non-palindromic portion of the original string in reverse at the beginning of s. This is done by slicing s[palindrome_length:] (the part that is not part of the palindrome) and reversing it, then concatenating it with the original string s.
Finally, the result is the shortest palindrome formed by adding the required characters to the front of s.

Let’s look at the code for the solution we just discussed.

def shortest_palindrome(s):
    concatenated = s + "#" + s[::-1]
    
    def get_prefix_array(concatenated):
        prefix = [0] * len(concatenated)
        j = 0
        for i in range(1, len(concatenated)):
            while j > 0 and concatenated[i] != concatenated[j]:
                j = prefix[j - 1]
            if concatenated[i] == concatenated[j]:
                j += 1
            prefix[i] = j
        return prefix
    palindrome_length = get_prefix_array(concatenated)[-1]
    result = s[palindrome_length:][::-1] + s
    return result
test_cases = [
    "aacecaaa",   # Expected: "aaacecaaa"
    "abcd",       # Expected: "dcbabcd"
    "racecar",    # Expected: "racecar"
    "a"          # Expected: "a"
]
for test in test_cases:
    print(f"Input: {test} -> Shortest Palindrome: {shortest_palindrome(test)}")

Time and space complexity

The time complexity of this approach is linear $O(n)$ , where $n$ is the length of the input string s. This is because the KMP algorithm computes the prefix array in linear time, and the subsequent operations are linear as well.
The space complexity is also linear $O(n)$ , as space is used to store the concatenated string and the prefix array.

You can explore Educative’s "Grokking the Coding Interview Patterns" and "Grokking Dynamic Programming Interview" courses, which include optimized strategies for problems like the shortest palindrome and many more.

Conclusion

The KMP algorithm approach is efficient and works in linear time compared to the brute force method, which has quadratic time complexity. By leveraging string-matching techniques, this solution optimally computes the shortest palindrome.

Frequently asked questions

Haven’t found what you were looking for? Contact Us

What is the shortest palindrome problem?

The shortest palindrome problem involves converting a given string into the shortest possible palindrome by adding characters to its beginning.

What is the brute force approach to solving the shortest palindrome problem?

The brute force approach reverses the string, checks for the longest palindrome substring at the start, and adds non-palindrome characters to the string’s beginning.

How does the KMP algorithm improve efficiency?

The KMP algorithm uses a prefix array to reduce redundant comparisons, resulting in a time complexity of $O(n)$ for the shortest palindrome problem.

What is the concatenation strategy in the KMP approach?

The KMP method concatenates the string, a delimiter (#), and the reversed string. It then calculates the prefix array to identify the longest palindromic prefix.

Free Resources