Repeatedly remove matching groups from both ends of a string until the ends differ.
Problem
You are given a string s. You may repeatedly perform the following operation:
- Choose a non-empty prefix of
sconsisting of the same character. - Choose a non-empty suffix of
sconsisting of the same character. - If the prefix and suffix are made of the same character, delete both at the same time.
Keep applying the operation as long as possible. Return the minimum possible length of the string after all valid deletions.
Goal
Compute the length of the shortest string that can remain after deleting similar ends from both sides.
Notes
- A prefix/suffix must be contiguous and made of one repeated character.
- The deleted prefix and suffix must use the same character.
- You do not need to output the remaining string itself, only its length.
Input Format
- A single string
s. scontains lowercase English letters.
Output Format
- Return a single integer: the minimum length achievable after deleting similar ends.
Constraints
sconsists of lowercase English letters only.
Example 1
Input
s = "ca"
Output
2
Explanation
The first and last characters are different, so no deletion is possible.
Example 2
Input
s = "cabaabac"
Output
0
Explanation
You can delete matching ends repeatedly until the string becomes empty.
Show 1 more example
Example 3
Input
s = "aabccabba"
Output
3
Explanation
After removing matching ends as much as possible, the remaining middle part has length 3.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.