263. Shortest Palindrome (Prepend Count)

Given a string s, you can convert it to a palindrome by adding characters in front of it. Return the minimum number of characters that must be prepended to make s a palindrome.

Input: A quoted string s.

Output: Integer — minimum characters to prepend.

Examples

Input: "aacecaaa"
Output: 1
Explanation: Prepend 'a' -> 'aaacecaaa'.

Input: "abcd"
Output: 3
Explanation: Prepend 'dcb'.

Input: ""
Output: 0
Explanation: Already a palindrome.

Constraints

• 0<=s.length<=5*10^4

Asked by