Minimum Length of String After Deleting Similar Ends

How it works

We can repeatedly trim matching characters from both ends of the string. The operation requires the prefix and suffix to consist of the same character, and we must remove at least one character from each end.

Using two pointers starting at opposite ends, we check if both point to the same character. If they do, we greedily remove all consecutive occurrences of that character from both ends. This greedy choice is optimal because removing more characters now can only help (or not hurt) future operations.

Steps

1. Initialize two pointers: l at the start and r at the end of the string.
2. While l < r and s[l] == s[r]:
   • Store the matching character.
   • Move l right past all consecutive occurrences of this character.
   • Move r left past all consecutive occurrences of this character.
3. The remaining length is r - l + 1.
4. If the pointers cross (l > r), the entire string was deleted, returning 0.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Allowing Pointers to Cross Without Proper Bounds

When moving pointers past consecutive matching characters, they can cross each other if the entire remaining string consists of the same character. The inner while loops must check l <= r to prevent accessing invalid indices or producing negative lengths.

Requiring Non-Empty Prefix and Suffix Separately

The operation removes a non-empty prefix and a non-empty suffix of the same character. A common mistake is allowing one side to be empty, which violates the problem constraints. Both pointers must move at least once per valid operation.

class Solution:
    def minimumLength(self, s: str) -> int:
        l, r = 0, len(s) - 1

        while l < r and s[l] == s[r]:
            tmp = s[l]
            while l <= r and s[l] == tmp:
                l += 1
            while l <= r and s[r] == tmp:
                r -= 1
        return r - l + 1

class Solution {
public:
    int minimumLength(string s) {
        int l = 0, r = s.length() - 1;

        while (l < r && s[l] == s[r]) {
            char tmp = s[l];
            while (l <= r && s[l] == tmp) {
                l++;
            }
            while (l <= r && s[r] == tmp) {
                r--;
            }
        }
        return r - l + 1;
    }
};