#214

Hard

LeetCode Problem Workspace

Shortest Palindrome

The Shortest Palindrome problem asks to transform a string into a palindrome by adding characters at the beginning, with the shortest possible result.

string rolling hash string matching hash function

Problem Statement

Given a string s, you need to transform it into a palindrome by adding characters only at the front. The goal is to perform this transformation with the fewest characters added, returning the shortest possible palindrome. The input string will only contain lowercase English letters.

For example, given s = "aacecaaa", the shortest palindrome formed by adding characters at the front is "aaacecaaa". Another example is s = "abcd", which results in "dcbabcd" when transformed into the shortest palindrome.

Examples

Example 1

Input: s = "aacecaaa"

Output: "aaacecaaa"

Example details omitted.

Example 2

Input: s = "abcd"

Output: "dcbabcd"

Example details omitted.

Constraints

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

Solution Approach

Prefix Search with Rolling Hash

The solution involves using rolling hash to efficiently find the longest palindromic prefix in the string. By calculating the hash of the string and comparing it with the reverse, we can determine the largest palindrome that can be formed by appending characters from the string's end.

String Matching and KMP Algorithm

We utilize the Knuth-Morris-Pratt (KMP) algorithm to efficiently find the longest palindromic prefix by performing a string matching operation. This approach avoids redundant comparisons and speeds up the process, leading to an optimal solution.

Efficient Prepend of Characters

Once the longest palindromic prefix is identified, we can prepend the remaining part of the string (that does not form a palindrome) in reverse order to the beginning of the string. This step guarantees the formation of the shortest palindrome.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity of the solution is O(n), where n is the length of the string. This is because the rolling hash and KMP algorithm each process the string in linear time. The space complexity is also O(n), as we store hash values and the reversed string for comparison.

What Interviewers Usually Probe

Understanding of rolling hash and string matching techniques.
Ability to implement optimal algorithms for palindrome construction.
Knowledge of the KMP algorithm and its application to string problems.

Common Pitfalls or Variants

Common pitfalls

Overcomplicating the solution by brute-forcing palindrome checks for each substring.
Failing to optimize the solution, leading to an O(n^2) time complexity due to repeated comparisons.
Not handling edge cases like an empty string or already palindromic strings efficiently.

Follow-up variants

Shortest palindrome with case-sensitive characters.
Transforming the string to a palindrome by adding characters at both ends.
Finding the shortest palindrome by appending characters at the end instead of the front.

FAQ

What is the main strategy for solving the Shortest Palindrome problem?

The main strategy involves using rolling hashes and string matching algorithms like KMP to identify the longest palindromic prefix and efficiently prepend characters to form the shortest palindrome.

How can I optimize the solution for the Shortest Palindrome problem?

You can optimize the solution by using a rolling hash combined with KMP for efficient string matching, which ensures an O(n) time complexity.

What are the time and space complexities of the solution?

The time complexity is O(n), and the space complexity is O(n), where n is the length of the string.

Can the Shortest Palindrome problem be solved with brute force?

While brute force is possible, it leads to a time complexity of O(n^2), which is inefficient. An optimal solution using rolling hash and KMP is much faster.

What happens if the input string is already a palindrome?

If the string is already a palindrome, no characters need to be added, and the original string will be returned as the shortest palindrome.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        base = 131
        mod = 10**9 + 7
        n = len(s)
        prefix = suffix = 0
        mul = 1
        idx = 0
        for i, c in enumerate(s):
            prefix = (prefix * base + (ord(c) - ord('a') + 1)) % mod
            suffix = (suffix + (ord(c) - ord('a') + 1) * mul) % mod
            mul = (mul * base) % mod
            if prefix == suffix:
                idx = i + 1
        return s if idx == n else s[idx:][::-1] + s

Solution 2: KMP Algorithm

According to the problem description, we need to reverse the string $s$ to obtain the string $\textit{rev}$, and then find the longest common part of the suffix of the string $\textit{rev}$ and the prefix of the string $s$. We can use the KMP algorithm to concatenate the string $s$ and the string $\textit{rev}$ and find the longest common part of the longest prefix and the longest suffix.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        base = 131
        mod = 10**9 + 7
        n = len(s)
        prefix = suffix = 0
        mul = 1
        idx = 0
        for i, c in enumerate(s):
            prefix = (prefix * base + (ord(c) - ord('a') + 1)) % mod
            suffix = (suffix + (ord(c) - ord('a') + 1) * mul) % mod
            mul = (mul * base) % mod
            if prefix == suffix:
                idx = i + 1
        return s if idx == n else s[idx:][::-1] + s

Continue Practicing

#187 repeated dna sequences #1392 longest happy prefix #1044 longest duplicate substring