Check If Word Is Valid After Substitutions

medium stack string simulation

Problem

We start with the empty string and may repeatedly insert the substring "abc" at any position. A string is valid if it can be produced this way. Given a string s, return true if it is valid. Equivalently, scanning left to right, every "abc" pattern that forms can be collapsed, and the whole string must reduce to empty.

Inputs = "aabcbc"

Outputtrue

"" → "abc" → "aabcbc": insert "abc" then insert another "abc" inside, so it is valid.

s (only letters a, b, c)

def is_valid(s):
    stack = []
    for ch in s:
        if ch == 'c':
            if len(stack) < 2 or stack[-1] != 'b' or stack[-2] != 'a':
                return False
            stack.pop()
            stack.pop()
        else:
            stack.append(ch)
    return len(stack) == 0

function isValid(s) {
  const stack = [];
  for (const ch of s) {
    if (ch === 'c') {
      const n = stack.length;
      if (n < 2 || stack[n - 1] !== 'b' || stack[n - 2] !== 'a') return false;
      stack.pop();
      stack.pop();
    } else {
      stack.push(ch);
    }
  }
  return stack.length === 0;
}

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char ch : s.toCharArray()) {
            if (ch == 'c') {
                if (stack.size() < 2) return false;
                char b = stack.pop();
                char a = stack.pop();
                if (a != 'a' || b != 'b') return false;
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

bool isValid(string s) {
    string stack;
    for (char ch : s) {
        if (ch == 'c') {
            int n = stack.size();
            if (n < 2 || stack[n - 1] != 'b' || stack[n - 2] != 'a') return false;
            stack.pop_back();
            stack.pop_back();
        } else {
            stack.push_back(ch);
        }
    }
    return stack.empty();
}

Explanation

A string is valid only if we can keep collapsing the pattern "abc" until nothing is left. A stack lets us do exactly that in one pass: whenever a freshly completed "abc" appears at the top, we erase it.

We scan left to right and push every character that is 'a' or 'b' onto the stack. When we see a 'c', it can only be valid if the two items directly under it are 'a' then 'b' — that means an "abc" just formed, so we pop() both of them.

If a 'c' shows up but the top two are not 'a','b', there is no "abc" to remove, so we immediately return false. After the scan, the string is valid only if the stack is completely empty.

Example: "aabcbc". Push a, a. At the first c, the top is b? no — actually we push a, a, b then the c collapses the inner abc (the second a, the b) leaving [a]; the next b is pushed and the final c collapses abc again, leaving an empty stack → true.

Each character is pushed or popped once, so the work is linear in the length of the string.

Time: O(n) Space: O(n)