Fewest Characters to Make a Palindrome
You get a string s of lowercase English letters. A palindrome is a string that reads the same from left to right and from right to left.
You may add characters only at the front of s. Return the smallest number of characters you must add so that the whole string becomes a palindrome.
If s is already a palindrome, return 0.
Hint
The part of s that you do not need to copy is the longest prefix of s that is already a palindrome. Checking every prefix one by one is O(n²). For O(n), look at the string s + "#" + reverse(s) and the prefix function from the KMP algorithm.
Examples
Example 1
- Input:
- "abab"
- Output:
- 1
The longest prefix that is a palindrome is "aba". Only the last "b" is left over, so add one "b" at the front: "babab".
Example 2
- Input:
- "race"
- Output:
- 3
Only "r" is a palindrome prefix. Add "e", "c" and "a" at the front to get "ecarace".
Example 3
- Input:
- "noon"
- Output:
- 0
"noon" is already a palindrome, so nothing needs to be added.
Constraints
0 <= s.length <= 40scontains only lowercase English letters.
Run checks your code against the 3 examples. Submit checks it against all 223 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.