Solution Explanation for Shortest Palindrome

This problem asks to find the shortest palindrome that can be formed by adding characters to the beginning of a given string. Two main approaches are commonly used: a rolling hash approach and a KMP (Knuth-Morris-Pratt) algorithm approach.

Solution 1: Rolling Hash

This approach efficiently finds the longest palindrome prefix of the input string. The core idea is to use a rolling hash to compare prefixes and suffixes of the string.

Algorithm:

1. Rolling Hash: A rolling hash function efficiently calculates the hash of a substring without recomputing the entire hash each time. We use a base (e.g., 131) and a modulus (e.g., 109 + 7) to prevent hash collisions.

2. Prefix and Suffix Hash: The algorithm calculates the rolling hash for prefixes and suffixes simultaneously. If the prefix and suffix hashes match up to a certain index idx, it indicates that the substring from 0 to idx is a palindrome.

3. Shortest Palindrome Construction: If idx equals the string length, the string is already a palindrome. Otherwise, the shortest palindrome is formed by reversing the remaining suffix (s[idx:]) and prepending it to the original string.

Time Complexity: O(n), where n is the length of the string. The rolling hash calculation iterates through the string once.

Space Complexity: O(1), as the algorithm uses only a constant amount of extra space.

Solution 2: KMP Algorithm

This approach utilizes the KMP algorithm, typically used for string searching, to find the longest proper prefix that is also a suffix.

Algorithm:

1. String Concatenation: Concatenate the input string s, a separator character (e.g., '#'), the reversed string s[::-1], and another separator (e.g., '$'). This creates a string t.

2. KMP Next Array: Construct the KMP next array for the concatenated string t. The next array stores the length of the longest proper prefix of a given substring that is also a suffix.

3. Longest Common Prefix-Suffix: The value next[n-1] (where n is the length of t) indicates the length of the longest proper prefix of t that is also a suffix. This corresponds to the longest palindrome prefix of the original string s.

4. Shortest Palindrome Construction: The shortest palindrome is constructed by taking the reversed substring of s from the length of the longest common prefix-suffix to the end, and prepending it to the original string s.

Time Complexity: O(n), where n is the length of the string. The KMP algorithm has a linear time complexity.

Space Complexity: O(n), due to the next array used in the KMP algorithm.

Code Examples (Python):

Solution 1 (Rolling Hash):

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):

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        t = s + "#" + s[::-1] + "$"
        n = len(t)
        next = [0] * n
        next[0] = -1
        i, j = 2, 0
        while i < n:
            if t[i - 1] == t[j]:
                j += 1
                next[i] = j
                i += 1
            elif j:
                j = next[j]
            else:
                next[i] = 0
                i += 1
        return s[::-1][: -next[-1]] + s
 

Both solutions provide efficient ways to solve the shortest palindrome problem, each with its own advantages in terms of space complexity. The rolling hash solution is generally preferred for its better space efficiency. However, the KMP approach offers a different algorithmic perspective and can be valuable for understanding string manipulation techniques.