123. Minimum Characters to Remove from Ends to Make a Palindrome
Minimum Characters to Remove from Ends to Make a Palindrome
Given a string, return the minimum number of characters to remove from the left end, the right end, or both ends so that the remaining string is a palindrome.
You may remove only characters from the two ends of the string. Characters in the middle cannot be removed unless they become part of an end after earlier removals.
The remaining string must be contiguous in the original string.
A palindrome is a string that reads the same forward and backward.
If the string is already a palindrome, return 0.
Method
int minimumCharactersToRemove(String s)
1 ≤ s.length() ≤ 100,000s consists of lowercase English letters.- You must keep a contiguous substring after removals.
- The answer is always between
0 and s.length() - 1, inclusive.
Notes
- Removing characters from both ends means removing some prefix and some suffix.
- The goal is equivalent to keeping the longest palindromic contiguous substring and removing everything outside it.
- A single character is a palindrome.
Examples
Example 1
Input: s = "abca"
Method Call: minimumCharactersToRemove(s = "abca")
Output: 3
Explanation: No palindromic contiguous substring longer than length 1 exists. So keep any one character such as "a", "b", or "c", and remove the other 3 characters.
Example 2
Input: s = "aabcb"
Method Call: minimumCharactersToRemove(s = "aabcb")
Output: 2
Explanation: The longest palindromic contiguous substring is "bcb". Remove the prefix "aa" to keep "bcb", so the minimum number of removed characters is 2.
Example 3
Input: s = "racecar"
Method Call: minimumCharactersToRemove(s = "racecar")
Output: 0
Explanation: The string is already a palindrome.
Example 4
Input: s = "abcdef"
Method Call: minimumCharactersToRemove(s = "abcdef")
Output: 5
Explanation: No palindrome longer than one character exists, so keep any one character and remove the other five.
Example 5
Input: s = "cabbad"
Method Call: minimumCharactersToRemove(s = "cabbad")
Output: 2
Explanation: Keep the contiguous palindrome "abba" by removing 'c' from the left and 'd' from the right.