Make a Palindrome by Inserting Characters

Given a string s, return the minimum number of characters needed to be inserted so that the string becomes a palindrome.

Constraints

• n ≤ 1,000 where n is the length of s

https://binarysearch.com/problems/Make-a-Palindrome-by-Inserting-Characters

Examples

Example 1

Input

• s = radr

Output

• answer = 1

Explanation

We can insert "a" to get "radar"

Solution