The shortest palindrome problem is an interesting coding challenge. Given a string `s`

, you are to find the shortest palindrome by adding characters to the start of the string.

Given a string `s`

, convert it to the shortest palindrome by adding characters to its beginning. For instance, if the input is `aacecaaa`

, the answer is `aaacecaaa`

.

The one palindrome we can find is by reversing the whole string, and adding it in a prefix of a string. In this case, it will be `aaacecaaaacecaaa`

. Since we have to find the shortest palindrome, we will follow 2 approaches in this Answer.

The most straightforward way to tackle this is:

Reverse the string to get the

`rev_s`

.Check for the substring from 0 to length of

`s`

in`rev_s`

which is a palindrome.Add the non-palindrome part of the substring to the beginning of

`s`

.

We will see the palindrome in the word `aacecaaa`

, using the steps mentioned above.

`s`

=`aacecaaa`

`rev_s`

=`aaacecaa`

Checking for a substring which is a palindrome, we got

`aacecaa`

Now, the non-palindrome part is

`a`

, adding it to the beginning of`s`

, our`s`

will become`aaacecaaa`

, which is the shortest palindrome.

def shortest_palindrome_bruteforce(s):n = len(s)s_rev = s[::-1]for i in range(n, 0, -1):if s[:i] == s[:i][::-1]:return s_rev[:n-i] + sreturn s_rev + s # If s has no palindrome substring at all.

print(shortest_palindrome_bruteforce("aacecaaa"))

Its time complexity is quadratic

$(O(n^2))$ due to nested loops iterating over prefixes and checking for palindromes.Its space complexity is linear

$(O(n))$ as it uses additional space to store the reversed string version.

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

The Knuth-Morris-Pratt (KMP) algorithm is famous for pattern searching. 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.

**Concatenate the strings:**Concatenate`s`

, a delimiter, and`rev_s`

. For the case of`aacecaaa`

, our`concatenated`

will be`aacecaaa#aaacecaa`

.

concatenated = s + "#" + s[::-1]

**Generate the prefix array using KMP:**For example, let's calculate the prefix array for the concatenated string`aacecaaa#aaacecaa`

. The prefix array at each index`i`

stores the length of the longest proper prefix that is also a suffix of the substring ending at the index`i`

. This array is computed using the KMP (Knuth-Morris-Pratt) string search algorithm. The output of the given code will be:`[0, 1, 0, 0, 1, 2, 2, 3, 4, 0, 1, 2, 3, 4, 5, 6, 7]`

. Here’s how you can build the prefix array:

def get_prefix_array(concatenated):prefix = [0] * len(concatenated)j = 0for i in range(1, len(concatenated)):while j > 0 and concatenated[i] != concatenated[j]:j = prefix[j - 1]if concatenated[i] == concatenated[j]:j += 1prefix[i] = jreturn prefixprint(get_prefix_array("aacecaaa#aaacecaa"))

**Obtain the shortest palindrome:**The last value in the prefix array gives us the length of the palindrome substring that starts from the first character of`s`

.

palindrome_length = get_prefix_array("aacecaaa#aaacecaa")[-1]print(palindrome_length)

To make

`s`

the shortest palindrome, we need to add the part of`s`

which is not a palindrome to the beginning of`s`

.

result = s[palindrome_length:][::-1] + s

Combining all the above steps, we get the following solution:

def shortest_palindrome(s):concatenated = s + "#" + s[::-1]def get_prefix_array(concatenated):prefix = [0] * len(concatenated)j = 0for i in range(1, len(concatenated)):while j > 0 and concatenated[i] != concatenated[j]:j = prefix[j - 1]if concatenated[i] == concatenated[j]:j += 1prefix[i] = jreturn prefixpalindrome_length = get_prefix_array(concatenated)[-1]result = s[palindrome_length:][::-1] + sreturn result

print(shortest_palindrome("aacecaaa"))

Its time complexity is linear

$(O(n))$ , where n is the length of the input string`s`

, as it constructs a prefix array using the KMP algorithm and performs subsequent operations based on the array.Its space complexity

$(O(n))$ due to the`concatenated`

string and the`prefix`

array.

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS