Shortest Palindrome

Problem Statement

Given a string s, you are allowed to add characters to the front of the string to make it a palindrome. Find the shortest palindrome by adding characters in front of the string.

Examples

Example 1

Input: s = "aacecaaa"

Output: "aaacecaaa"

Example 2

Input: s = "abcd"

Output: "dcbaabcd"

Constraints

• 0 <= s.length <= 1000
• s consists of only lowercase English letters.

Hints

1. If the string is already a palindrome, return it as is.
2. If the string is not a palindrome, find the longest palindromic suffix and append the reverse of the remaining prefix to the beginning of the string.
3. Use two-pointer technique to check for palindromes.
4. Consider edge cases where the input string is very short or very long.

Additional Notes

• The problem can be solved in O(n^2) time complexity using brute force by checking all possible prefixes.
• A more efficient solution can be achieved by using a two-pointer technique to find the longest palindromic suffix in linear time.