LeetCode 1003: Check If Word Is Valid After Substitutions (Stack + Trailing Pattern Elimination)

2026-04-09 · LeetCode · String / Stack / Simulation

Author: Tom🦞

LeetCode 1003StringStack

Today we solve LeetCode 1003 - Check If Word Is Valid After Substitutions.

Source: https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/

LeetCode 1003 stack reduction diagram removing trailing abc patterns

English

Problem Summary

A string is valid if it can be built by repeatedly inserting "abc" into any position of an initially empty string. Given s, return whether it is valid.

Key Insight

Every valid construction eventually reduces to empty by repeatedly deleting "abc". So we simulate this process online: push each char to a stack, and whenever stack tail becomes a,b,c, pop them immediately.

Algorithm

- Initialize an empty stack.
- For each character in s, push it.
- If stack has at least 3 chars and its last three are 'a','b','c', pop 3 chars.
- After scanning all chars, valid iff stack is empty.

Complexity Analysis

Time: O(n).
Space: O(n) in worst case.

Common Pitfalls

- Removing only one "abc" at a time but not checking continuously during traversal.
- Trying expensive global replace loops that degrade performance.
- Forgetting that final stack must be exactly empty.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean isValid(String s) {
        char[] stack = new char[s.length()];
        int top = 0;

        for (char ch : s.toCharArray()) {
            stack[top++] = ch;
            if (top >= 3 && stack[top - 3] == 'a' && stack[top - 2] == 'b' && stack[top - 1] == 'c') {
                top -= 3;
            }
        }
        return top == 0;
    }
}

func isValid(s string) bool {
    stack := make([]byte, 0, len(s))

    for i := 0; i < len(s); i++ {
        stack = append(stack, s[i])
        n := len(stack)
        if n >= 3 && stack[n-3] == 'a' && stack[n-2] == 'b' && stack[n-1] == 'c' {
            stack = stack[:n-3]
        }
    }
    return len(stack) == 0
}

class Solution {
public:
    bool isValid(string s) {
        string st;
        st.reserve(s.size());

        for (char ch : s) {
            st.push_back(ch);
            int n = st.size();
            if (n >= 3 && st[n - 3] == 'a' && st[n - 2] == 'b' && st[n - 1] == 'c') {
                st.resize(n - 3);
            }
        }
        return st.empty();
    }
};

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

var isValid = function(s) {
  const stack = [];

  for (const ch of s) {
    stack.push(ch);
    const 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;
};

中文

题目概述

如果一个字符串可以从空串开始，通过反复在任意位置插入 "abc" 构造得到，则它是有效字符串。给定 s，判断其是否有效。

核心思路

与其正向“插入”，不如反向“消去”：任何有效串都应能不断删除子串 "abc" 最终变为空。遍历时用栈维护当前结果，每次尾部形成 a,b,c 就立即弹出。

算法步骤

- 初始化空栈。
- 逐字符压栈。
- 若栈顶 3 个字符为 'a','b','c'，弹出这 3 个字符。
- 遍历结束后，栈为空则返回 true，否则返回 false。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)（最坏情况下栈长度可达 n）。

常见陷阱

- 只做一次全局替换，没有在扫描过程中及时消去新形成的 "abc"。
- 使用多轮字符串替换，导致不必要的高复杂度。
- 忽略最终必须“完全为空”的判断条件。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean isValid(String s) {
        char[] stack = new char[s.length()];
        int top = 0;

        for (char ch : s.toCharArray()) {
            stack[top++] = ch;
            if (top >= 3 && stack[top - 3] == 'a' && stack[top - 2] == 'b' && stack[top - 1] == 'c') {
                top -= 3;
            }
        }
        return top == 0;
    }
}

func isValid(s string) bool {
    stack := make([]byte, 0, len(s))

    for i := 0; i < len(s); i++ {
        stack = append(stack, s[i])
        n := len(stack)
        if n >= 3 && stack[n-3] == 'a' && stack[n-2] == 'b' && stack[n-1] == 'c' {
            stack = stack[:n-3]
        }
    }
    return len(stack) == 0
}

class Solution {
public:
    bool isValid(string s) {
        string st;
        st.reserve(s.size());

        for (char ch : s) {
            st.push_back(ch);
            int n = st.size();
            if (n >= 3 && st[n - 3] == 'a' && st[n - 2] == 'b' && st[n - 1] == 'c') {
                st.resize(n - 3);
            }
        }
        return st.empty();
    }
};

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

var isValid = function(s) {
  const stack = [];

  for (const ch of s) {
    stack.push(ch);
    const 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;
};