# LeetCode 1003: Check If Word Is Valid After Substitutions

## Problem Restatement

We are given a string `s`.

A string is valid if we can repeatedly remove the substring `"abc"` from it until the string becomes empty.

We need to return `true` if `s` is valid, and `false` otherwise.

The official constraints state that `1 <= s.length <= 2 * 10^4` and `s` consists only of letters `a`, `b`, and `c`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | String `s` consisting of `a`, `b`, `c` |
| Output | `true` if valid, `false` otherwise |
| Valid | Repeated removal of `"abc"` reduces to empty |

Function shape:

```python
def isValid(s: str) -> bool:
    ...
```

## Examples

Example 1:

```python
s = "aabcbc"
```

Remove `"abc"` from positions 1-3: `"aabcbc"` → `"abc"` → `""`

Answer:

```python
True
```

Example 2:

```python
s = "abcabcababcc"
```

Remove leftmost `"abc"`: `"abcabcababcc"` → `"abcababcc"` → `"ababcc"` → `"abcc"` → `"abc"` → `""`

Answer:

```python
True
```

Example 3:

```python
s = "abccba"
```

No `"abc"` substring remains after any step without creating a dead end.

Answer:

```python
False
```

## Key Insight

We can use a stack to simulate the removal process without repeatedly scanning the string.

Push characters onto the stack one at a time.

Whenever the top three characters of the stack are `"a"`, `"b"`, `"c"` (from bottom to top), pop all three.

This works because `"abc"` must be contiguous, and the stack naturally simulates the removal in the right order.

## Algorithm

1. Initialize an empty stack.
2. For each character `ch` in `s`:
   - Push `ch`.
   - If the top three stack elements are `['a', 'b', 'c']`, pop all three.
3. Return `true` if the stack is empty.

## Correctness

When we push a character and the top three stack elements form `"abc"`, this means the last three characters of the string processed so far form `"abc"`. Removing them is correct because they are contiguous.

After this removal, the characters below them in the stack are revealed. If they also form `"abc"` now, the next iteration of the same step handles them.

Since every valid string reduces to empty via repeated `"abc"` removals, and the stack processes each removal in left-to-right order, the stack approach correctly identifies all valid strings.

An invalid string leaves leftover characters in the stack.

## Edge Cases

- The stack should store exactly the unresolved items needed by the invariant.
- Process equal values deliberately; many monotonic-stack problems differ only in `<` versus `<=`.
- Flush or inspect the remaining stack after the scan if unresolved items still contribute to the answer.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each character is pushed and popped at most once |
| Space | `O(n)` | Stack can hold at most `n` characters |

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

```python
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 len(stack) == 0
```

## Code Explanation

We process each character by pushing it:

```python
stack.append(ch)
```

After each push, check if the top three form `"abc"`:

```python
if len(stack) >= 3 and stack[-3:] == ['a', 'b', 'c']:
    stack.pop()
    stack.pop()
    stack.pop()
```

If the stack is empty at the end, all characters were removed via valid `"abc"` deletions:

```python
return len(stack) == 0
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.isValid("aabcbc") == True
    assert s.isValid("abcabcababcc") == True
    assert s.isValid("abccba") == False
    assert s.isValid("abc") == True
    assert s.isValid("ab") == False
    assert s.isValid("aabbcc") == False

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `"aabcbc"` | `True` | Reduces to empty |
| `"abcabcababcc"` | `True` | Multiple nested removals |
| `"abccba"` | `False` | Cannot reduce to empty |
| `"abc"` | `True` | Single removal |
| `"ab"` | `False` | Too short to contain `"abc"` |
| `"aabbcc"` | `False` | Characters not contiguous in right order |