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 * 10⁴
s consists of lowercase English letters only.