Given a string, you may insert new characters at any positions (front, back, or between existing characters). Determine the minimum number of insertions needed so that the string becomes a palindrome (reads the same forwards and backwards). You only need the minimum count, not the resulting palindrome, so the answer is unique.
For example, ab needs one insertion (insert a at the end to get aba, or b at the front to get bab), so the answer is 1. A string that is already a palindrome needs 0 insertions.
A single line containing the string, made up of lowercase English letters.
A single integer: the minimum number of character insertions required to turn the input into a palindrome.
a-z.Example 1
Input
ab
Expected
1
Explanation
Insert one character (for example a at the end to make aba), so 1 insertion suffices.
Example 2
Input
abcda
Expected
2
Explanation
The outer a's already match. Inside, bcd needs 2 insertions (e.g. b and d) to become a palindrome such as bdcdb, so the total is 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →