276. Minimum Insertions to Make a Palindrome

Given a string s, return the minimum number of characters you must insert anywhere to make s a palindrome.

Input: A quoted string s.

Output: Integer — minimum insertions.

Examples

Example 1

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

Example 2

Input: "mbadm"
Output: 2
Explanation: 'mbdadbm' or similar with 2 inserts.

Example 3

Input: "leetcode"
Output: 5
Explanation: Five insertions needed.