1003. Check If Word Is Valid After Substitutions

• Time:
• Space:

C++JavaPython

class Solution {
 public:
  bool isValid(string s) {
    stack<char> stack;

    for (const char c : s)
      if (c == 'c') {
        if (stack.size() < 2)
          return false;
        if (stack.top() != 'b')
          return false;
        stack.pop();
        if (stack.top() != 'a')
          return false;
        stack.pop();
      } else {
        stack.push(c);
      }

    return stack.empty();
  }
};

class Solution {
  public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();

    for (final char c : s.toCharArray())
      if (c == 'c') {
        if (stack.size() < 2)
          return false;
        if (stack.peek() != 'b')
          return false;
        stack.pop();
        if (stack.peek() != 'a')
          return false;
        stack.pop();
      } else {
        stack.push(c);
      }

    return stack.isEmpty();
  }
}

class Solution:
  def isValid(self, s: str) -> bool:
    stack = []

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

    return not stack