Minimum Length of String After Deleting Similar Ends
Given a string s consisting only of characters 'a', 'b', and 'c', apply the following algorithm on the string any number of times:
- Pick a non-empty prefix from the string
swhere all the characters in the prefix are equal. - Pick a non-empty suffix from the string
swhere all the characters in this suffix are equal. - The prefix and the suffix should not intersect at any index.
- The characters from the prefix and suffix must be the same.
- Delete both the prefix and the suffix.
Return the minimum length of s after performing the above operation any number of times, possibly zero times.
Example 1
Input
s = "ca"Output
2You can't remove any characters, so the string stays as is.
Example 2
Input
s = "cabaabac"Output
0An optimal sequence removes matching ends in order until the string becomes empty.
Constraints
- 1 <= s.length <= 10^5
- s only consists of characters 'a', 'b', and 'c'.