Pad a Word Into a Palindrome

A puzzle app lets you insert letters anywhere in the word s (at the front, the back, or between letters). Return the fewest insertions needed to turn s into a palindrome.

Examples

Input:  s = "banana"
Output: 1
Explanation: add "b" at the end to get "bananab".

Input:  s = "race"
Output: 3
Explanation: "ecarace" is one way.

Input:  s = "noon"
Output: 0

Constraints

• 1 <= len(s) <= 300
• s consists of lowercase letters.
• Target complexity: O(n**2).

Goals

• Solve the problem for every substring, shortest first
• Decide whether the outer letters already pair up or one needs a partner inserted