Add zero or more characters to the beginning of s to make a palindrome, which reads the same in both directions. Return the shortest resulting palindrome.
Example 1:
Input: s = "ab"
Output: "bab"Explanation: Prepend "b" to obtain "bab". The original "ab" is not a palindrome, so adding one character is optimal.
Example 2:
Input: s = "racecar"
Output: "racecar"Explanation: The string already reads the same forwards and backwards, so add nothing.
Example 3:
Input: s = ""
Output: ""Explanation: The empty string is already a palindrome and needs no added characters.
Constraints:
0 <= s.length <= 50000- Only lowercase English letters occur.