Code Implementation

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for ch in s:
            stack.append(ch)
            if len(stack) >= 3 and stack[-3:] == ['a', 'b', 'c']:
                stack.pop()
                stack.pop()
                stack.pop()
        return not stack
      

class Solution {
public:
    bool isValid(string s) {
        vector<char> stack;
        for (char ch : s) {
            stack.push_back(ch);
            int n = stack.size();
            if (n >= 3 && stack[n-3] == 'a' && stack[n-2] == 'b' && stack[n-1] == 'c') {
                stack.pop_back();
                stack.pop_back();
                stack.pop_back();
            }
        }
        return stack.empty();
    }
};
      

class Solution {
    public boolean isValid(String s) {
        StringBuilder stack = new StringBuilder();
        for (char ch : s.toCharArray()) {
            stack.append(ch);
            int n = stack.length();
            if (n >= 3 && stack.charAt(n-3) == 'a' && stack.charAt(n-2) == 'b' && stack.charAt(n-1) == 'c') {
                stack.delete(n-3, n);
            }
        }
        return stack.length() == 0;
    }
}
      

var isValid = function(s) {
    let stack = [];
    for (let ch of s) {
        stack.push(ch);
        let n = stack.length;
        if (n >= 3 && stack[n-3] === 'a' && stack[n-2] === 'b' && stack[n-1] === 'c') {
            stack.pop();
            stack.pop();
            stack.pop();
        }
    }
    return stack.length === 0;
};
      

Problem Description

Given a string s consisting only of the characters 'a', 'b', and 'c', you are allowed to repeatedly perform the following operation as many times as possible:

• Remove any substring equal to "abc" from s.

Return true if s is empty after performing the above operation as many times as possible. Otherwise, return false.

Constraints:

• Only "abc" may be removed in one operation.
• Substrings can overlap, but each removal is for a contiguous "abc".
• All removals are applied until no more "abc" remains.
• Input string length: 1 ≤ s.length ≤ 20,000.

Thought Process

The problem asks whether we can remove all characters from s by repeatedly deleting "abc" substrings. At first glance, one might consider brute-force approaches:

• Repeatedly searching for "abc" in s and removing it, then checking again until no "abc" remains.

Instead, notice that every valid removal must be in the order "a" followed by "b" followed by "c", and removals can overlap. This suggests that we can process the string in a single pass, simulating the removals with a stack. Each time the top three elements of the stack form "abc", we remove them, as if we've found a valid substring to delete.

This stack-based approach efficiently models the process, ensuring we only remove valid "abc" substrings and handle overlaps naturally.

Solution Approach

Let's describe the solution step by step:

1. Initialize a stack: Start with an empty stack to keep track of the processed characters.
2. Iterate over the input string: For each character in s:
   • Push the character onto the stack.
   • After each push, check if the top three elements in the stack are ['a', 'b', 'c'] (in that order).
   • If so, remove (pop) these three characters from the stack. This simulates removing "abc" from the string.
3. Final check: After processing all characters, if the stack is empty, it means all characters were removed in valid "abc" groups, so return true. Otherwise, return false.

Why use a stack? The stack helps us efficiently keep track of the last few characters and quickly identify when an "abc" can be removed, all in a single pass through the string. Stack operations (push and pop) are O(1), making this approach efficient.

Example Walkthrough

Let's walk through an example with s = "aabcbc":

1. Stack: []
2. Read 'a': Stack = ['a']
3. Read 'a': Stack = ['a', 'a']
4. Read 'b': Stack = ['a', 'a', 'b']
5. Read 'c': Stack = ['a', 'a', 'b', 'c']
6. Now, top three are ['a', 'b', 'c'] (positions 1,2,3 from the end). Remove them: Stack = ['a']
7. Read 'b': Stack = ['a', 'b']
8. Read 'c': Stack = ['a', 'b', 'c']
9. Again, top three are ['a', 'b', 'c']. Remove them: Stack = []

Stack is empty at the end, so we return true.

Time and Space Complexity

• Brute-force approach: If we repeatedly search and remove "abc" substrings, each removal could take O(n), and there could be up to O(n) removals, leading to O(n^2) time complexity.
• Optimized stack approach:
  • Time Complexity: O(n), where n is the length of s. Each character is pushed and possibly popped at most once.
  • Space Complexity: O(n) in the worst case (if no "abc" is ever removed).

Summary

The key insight is that we can efficiently simulate the removal of "abc" substrings using a stack, processing the string in a single pass. This avoids the inefficiency of repeated searches and removals, and naturally handles overlaps. The stack approach is both simple and elegant, making it ideal for this type of sequential substring removal problem.