654. Trimming Matching Ends
A lowercase string is given. One MOVE chooses a letter c and removes a non-empty run of
c from the FRONT together with a non-empty run of the same c from the BACK, the two runs not
overlapping.
Print the shortest length the string can be reduced to.
ca -> 2 the ends differ, so no move is possible
cabaabac -> 0
aabccabba -> 3
## A move is only possible when the ends match
The chosen letter must appear at both ends, so a move exists exactly when the first and last characters are equal and the string has at least two characters.
## The sweep
i = 0, j = len-1
while i < j and s[i] == s[j]:
c = s[i]
while i <= j and s[i] == c: i += 1
while j >= i and s[j] == c: j -= 1
answer: j - i + 1, or 0 when i > j
## Why removing the WHOLE run is safe
A move may remove any non-empty prefix run and any non-empty suffix run, so partial removals are allowed and the greedy takes everything.
Taking less never helps. Whatever is left of that run still consists of the same letter, so the next move from the same position could only remove more of it, and the intermediate state is reachable from the greedy one. So the greedy reaches at least as short a string, and it is the one that needs no search.
The brute force that tries every prefix and suffix length agrees with it on every string tested, which is how that claim was checked rather than assumed.
## The inner loops must stop at each other
while i <= j and while j >= i are what stop the two runs from crossing and double counting.
On aaa the front run consumes everything, i becomes 3, and the back loop then does nothing
because j is already below i. The answer is 0.
Writing the inner loops without those bounds lets both pass each other and produces a negative length.
## The case that ends without emptying
aabccabba: the ends are both a, so the two a runs go, leaving bccabb. The ends are both
b, so those runs go, leaving cca. Now c and a differ and nothing more can be done, so
the answer is 3.
## Boundaries
A single character cannot be moved at all, because the prefix and suffix runs would overlap, so the answer is 1.
A string of one repeated letter goes to 0.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ length ≤ 200000` - the string contains only lowercase letters
Input
One line containing a non-empty string of lowercase letters.
Output
Print one integer, the shortest length reachable.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.