A mural strip is described by a string of lowercase letters. You may insert new characters at any positions. Find the minimum number of insertions required to make the whole string a palindrome (a string that reads the same forwards and backwards).
Line 1: the strip string s.
A single integer: the minimum number of insertions to make s a palindrome.
s <= 40s consists of lowercase English letters only.Example 1
Input
ab
Expected
1
Explanation
Insert one character (e.g. a at the end to form aba, or b at the front to form bab), so 1 insertion suffices.
Example 2
Input
race
Expected
3
Explanation
All four characters are distinct, so the longest palindromic subsequence has length 1; 3 insertions are required.
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 →