Minimum Insertions to Make String Palindrome

Given a nonempty lowercase-English string s, return the fewest characters that must be inserted at arbitrary positions to make the whole string a palindrome.…

Given a nonempty lowercase-English string s, return the fewest characters that must be inserted at arbitrary positions to make the whole string a palindrome. Existing characters retain their order and cannot be replaced or deleted. Return only the insertion count, not a constructed palindrome. A palindrome reads the same backward and forward. An already-palindromic string needs zero insertions.

- 1 <= s.length <= 1000. - s contains only lowercase English letters a through z. - The visualizer accepts 1..8 letters; longer valid inputs are coding-only.

Example 1: input s = "abcaa"; output 2. Insert c and b in suitable positions to obtain abcacba. Two insertions are necessary.

Example 2: input s = "ba"; output 1. Insert a before ba to obtain aba.

Example 3: input s = "racecar"; output 0. The whole input is already a palindrome, so no insertion is needed.

Category: Strings. Topic: dynamic-programming. Difficulty: hard. Patterns: dynamic-programming.