Shortest Palindrome

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. For example:

1. If s = "aacecaaa", the output should be "aaacecaaa".
2. If s = "abcd", the output should be "dcbabcd".

Explain how to solve this problem using an efficient algorithm like KMP, and provide a Python code implementation. Discuss the time and space complexity of your solution.

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        # Naive solution (Brute force)
        # Try all prefixes of s and check if they are palindromes
        # If a prefix is a palindrome, then reverse the remaining substring
        # and prepend it to s
        # This approach has a time complexity of O(n^2)
        
        # Optimized solution using KMP algorithm
        # We can construct a new string t = s + '#' + s[::-1]
        # Then, we can use the KMP algorithm to find the longest prefix of t that is also a suffix of t
        # The length of this prefix is the length of the longest palindrome prefix of s
        # Then, we can reverse the remaining substring of s and prepend it to s
        
        t = s + '#' + s[::-1]
        n = len(t)
        
        # Compute the prefix function (LPS array) for the KMP algorithm
        lps = [0] * n
        
        length = 0  # Length of the previous longest prefix suffix
        i = 1
        
        while i < n:
            if t[i] == t[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        
        # The length of the longest palindrome prefix of s is lps[n - 1]
        longest_palindrome_prefix_len = lps[n - 1]
        
        # Reverse the remaining substring of s and prepend it to s
        remaining_substring = s[longest_palindrome_prefix_len:]
        reversed_substring = remaining_substring[::-1]
        
        return reversed_substring + s

Explanation:

The problem requires us to find the shortest palindrome that can be formed by adding characters to the beginning of the input string s. A brute-force approach would involve checking all prefixes of s to see if they are palindromes. If a palindrome prefix is found, the remaining part of the string is reversed and prepended to s. This however leads to O(n^2) complexity. Instead, we can use the Knuth-Morris-Pratt (KMP) algorithm to solve this efficiently.

1. KMP Algorithm: The KMP algorithm helps find the longest prefix of a string that is also a suffix. This is crucial for finding the longest palindrome prefix in our case.

2. String Construction: We create a new string t by concatenating s, a separator #, and the reverse of s. For example, if s = "aacecaaa", then t = "aacecaaa#aaacecaa".

3. LPS Array: We compute the Longest Proper Prefix which is also a Suffix (LPS) array for t. lps[i] stores the length of the longest proper prefix of t[0...i] that is also a suffix of t[0...i].

4. Finding the Longest Palindrome Prefix: The last element of the LPS array, lps[n-1], gives the length of the longest palindrome prefix of s.

5. Constructing the Shortest Palindrome: The remaining part of s after the longest palindrome prefix is reversed and prepended to s to create the shortest palindrome.

Example:

Let's take s = "aacecaaa" as an example:

1. t = "aacecaaa#aaacecaa"
2. The LPS array for t is [0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7]
3. lps[len(t) - 1] = lps[15] = 7
4. The longest palindrome prefix of s has length 7, which is "aacecaa"
5. The remaining substring of s is "aa"
6. The reverse of the remaining substring is "aa"
7. The shortest palindrome is "aa" + "aacecaaa" = "aaacecaaa"

Big(O) Run-time Analysis:

The KMP algorithm's time complexity is O(n), where n is the length of the constructed string t. Constructing the string t takes O(n) time, and computing the LPS array also takes O(n) time. Reversing the remaining substring is also O(n). Therefore, the overall time complexity is O(n).

Big(O) Space Usage Analysis:

The space complexity is O(n) because we store the LPS array of size n, where n is the length of the constructed string t. The constructed string t also takes O(n) space. Therefore, the overall space complexity is O(n).

Edge Cases:

1. Empty String: If the input string s is empty, the shortest palindrome is an empty string.
2. Already a Palindrome: If the input string s is already a palindrome, the shortest palindrome is s itself.
3. Single Character String: If the input string s has only one character, the shortest palindrome is s itself.
4. String with No Palindrome Prefix: For example, s = "abcd". In this case, the LPS array will be mostly zeros, and the algorithm correctly prepends the reversed string to create the shortest palindrome.

Here's the code with the edge cases considered:

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        
        if s == s[::-1]:
            return s
        
        t = s + '#' + s[::-1]
        n = len(t)
        
        lps = [0] * n
        length = 0
        i = 1
        
        while i < n:
            if t[i] == t[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        
        longest_palindrome_prefix_len = lps[n - 1]
        remaining_substring = s[longest_palindrome_prefix_len:]
        reversed_substring = remaining_substring[::-1]
        
        return reversed_substring + s