Problem Description

Given a string s, you are allowed to repeatedly delete characters from both ends of the string as long as the characters at both ends are equal (i.e., s[0] == s[n-1]). In each operation, you remove all consecutive characters from the start and all consecutive characters from the end that are equal to each other. You must stop once the characters at the two ends are different or the string becomes empty.

Your task is to return the minimum length of the string that remains after performing this operation as many times as possible.

• You must not remove characters from the middle of the string.
• Each operation must be performed on the current ends of the string.
• There is only one valid way to perform the operation at each step.

Constraints:

• 1 <= s.length <= 105
• s consists only of lowercase English letters.

Thought Process

Let's break down the problem by thinking about how we can remove characters from both ends. At each step, if the first and last characters are equal, we can remove all consecutive occurrences of that character from both the start and the end. We repeat this process until the two ends have different characters or there is nothing left.

The brute-force approach would be to actually create new strings after every operation, but that would be inefficient for large strings. Instead, we can use two pointers: one starting from the left and one from the right, and move them inward as long as the current characters are equal.

The key insight is that we don't need to actually remove characters from the string; we just need to keep track of the current "active" substring using indices.

Solution Approach

The optimal solution uses a two-pointer technique to efficiently process the string:

1. Initialize two pointers: left = 0 and right = len(s) - 1.
2. While left < right and s[left] == s[right]:
   • Let ch = s[left] (the current character at both ends).
   • Move left forward as long as s[left] == ch.
   • Move right backward as long as s[right] == ch.
3. When the loop ends, the remaining substring is from left to right (inclusive).
4. The minimum length is right - left + 1 if left <= right, otherwise 0.

This approach is efficient because each character is only visited at most once from each end, and we avoid creating new strings.

Example Walkthrough

Example: s = "aabccabba"

1. Initial: left = 0, right = 8, s[left] = 'a', s[right] = 'a'.
2. Both ends are 'a'. Move left rightward past all 'a's:
   • left = 0 ('a'), left = 1 ('a'), left = 2 ('b')
   Move right leftward past all 'a's:
   • right = 8 ('a'), right = 7 ('b')
3. Now left = 2 ('b'), right = 7 ('b'). Both ends are 'b'. Move left rightward:
   • left = 2 ('b'), left = 3 ('c')
   Move right leftward:
   • right = 7 ('b'), right = 6 ('a')
4. Now left = 3 ('c'), right = 6 ('a'). Ends are different, so we stop.
5. Resulting substring is from left = 3 to right = 6: "ccab". Length = 4.

Time and Space Complexity

Brute-force approach: If we repeatedly create new substrings, each operation could take O(n) time, leading to O(n^2) in the worst case.

Optimized two-pointer approach: Each character is visited at most once by either pointer, so the total time complexity is O(n), where n is the length of the string. Space complexity is O(1) since we only use pointers and do not allocate extra space proportional to the input size.

Summary

The problem is efficiently solved using a two-pointer approach, where we move inward from both ends as long as the characters match, skipping all consecutive matching characters at each end. This avoids unnecessary string copying and ensures linear time performance. The key insight is to work with indices rather than modifying the string, making the solution both simple and efficient.

Code Implementation

class Solution:
    def minimumLength(self, s: str) -> int:
        left, right = 0, len(s) - 1
        while left < right and s[left] == s[right]:
            ch = s[left]
            while left <= right and s[left] == ch:
                left += 1
            while right >= left and s[right] == ch:
                right -= 1
        return right - left + 1 if left <= right else 0
      

class Solution {
public:
    int minimumLength(string s) {
        int left = 0, right = s.size() - 1;
        while (left < right && s[left] == s[right]) {
            char ch = s[left];
            while (left <= right && s[left] == ch) ++left;
            while (right >= left && s[right] == ch) --right;
        }
        return left <= right ? right - left + 1 : 0;
    }
};
      

class Solution {
    public int minimumLength(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right && s.charAt(left) == s.charAt(right)) {
            char ch = s.charAt(left);
            while (left <= right && s.charAt(left) == ch) left++;
            while (right >= left && s.charAt(right) == ch) right--;
        }
        return left <= right ? right - left + 1 : 0;
    }
}
      

var minimumLength = function(s) {
    let left = 0, right = s.length - 1;
    while (left < right && s[left] === s[right]) {
        let ch = s[left];
        while (left <= right && s[left] === ch) left++;
        while (right >= left && s[right] === ch) right--;
    }
    return left <= right ? right - left + 1 : 0;
};