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.

SOLUTION:

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        n = len(s)
        for i in range(n, -1, -1):
            if s[:i] == s[:i][::-1]:
                return s[i:][::-1] + s