214. Shortest Palindrome

Give a string S, we are asked to add a string P in front of S to make the new string PS a palindrome. if PS is a palindrome, then PS = PQP' where Q is a palindrome && P' is the reverse string of P. To find the shortest P is same as finding the longest Q in S.

PS = PQP' where P is the string to be added and Q is the longest palindrome in S.

Algorithm: Given a string S, append the reverse string of S to S

SS' = QPP'Q'
since Q is a palindrome, Q' = Q, so SS' = QPP'Q

We wnat to find the longest Q where Q is the prefix of S. Meanwhile Q is also a suffix of S'

an O(n ^ 2) solution

check longest palindrome substring from s

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        n = len(s)
        for i in range(n, 0, -1):
            if self.isPalindrome(s[:i]):
                # Add the reverse of the suffix in front of the original string
                return s[i:][::-1] + s
        return s[::-1] + s  # This handles the case when the string is empty or all characters need to be added

    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

# Example usage
solution = Solution()
s = "aacecaaa"
print(solution.shortestPalindrome(s))  # Output: "aaacecaaa"

string shortestPalindrome(string s) {
        string t = s;
        reverse(t.begin(), t.end());
        
        int len = s.length();
        for (; len >= 0; len--) {
            if (s.substr(0, len) == t.substr(t.length() - len)) {
                break;
            }
        }
        
        return t.substr(0, t.length() -len) + s;
    }

214. Shortest Palindrome - cocoder39/coco39_LC GitHub Wiki