214. 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.

Example 1:

Input: s = "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: s = "abcd"
Output: "dcbabcd"

Constraints:

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

Approach 01:

class Solution {
public:
    string shortestPalindrome(string inputString) {
        const string reversedString = {inputString.rbegin(), inputString.rend()};
        const string_view originalView(inputString);
        const string_view reversedView(reversedString);

        // Check the longest palindromic prefix
        for (int i = 0; i < inputString.length(); ++i) {
            if (originalView.substr(0, inputString.length() - i) == reversedView.substr(i)) {
                return reversedString.substr(0, i) + inputString;
            }
        }

        return reversedString + inputString;
    }
};

class Solution:
    def shortestPalindrome(self, inputString: str) -> str:
        reversedString = inputString[::-1]
        
        # Find the longest palindromic prefix
        for i in range(len(inputString)):
            if inputString[:len(inputString) - i] == reversedString[i:]:
                return reversedString[:i] + inputString
        
        return reversedString + inputString

Time Complexity

• Reversing the String:

  Reversing the input string takes \(O(n)\) time, where \(n\) is the length of the input string.

• Checking the Palindromic Prefix:

  The code iterates through the input string and checks for the longest palindromic prefix. For each iteration, comparing substrings takes \(O(n – i)\), where \(i\) is the current index. In the worst case, this results in a total time complexity of \(O(n^2)\) for this step.

• Overall Time Complexity:

  The overall time complexity is dominated by the palindromic prefix check, making it \(O(n^2)\), where \(n\) is the length of the input string.

Space Complexity

• Reversed String:

  Storing the reversed version of the input string requires \(O(n)\) space, where \(n\) is the length of the input string.

• Additional Variables:

  Other variables like the original and reversed string views are pointers to the input string, so they do not take up significant additional space.

• Overall Space Complexity:

  The overall space complexity is \(O(n)\), due to the space needed for storing the reversed string.