> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/string/1003.-check-if-word-is-valid-after-substitutions.md).

# 1003. Check If Word Is Valid After Substitutions

We are given that the string `"abc"` is valid.

From any valid string `V`, we may split `V` into two pieces `X` and `Y` such that `X + Y` (`X` concatenated with `Y`) is equal to `V`.  (`X` or `Y` may be empty.)  Then, `X + "abc" + Y` is also valid.

If for example `S = "abc"`, then examples of valid strings are: `"abc", "aabcbc", "abcabc", "abcabcababcc"`.  Examples of **invalid** strings are: `"abccba"`, `"ab"`, `"cababc"`, `"bac"`.

Return `true` if and only if the given string `S` is valid.

**Example 1:**

```
Input: "aabcbc"
Output: true
Explanation: 
We start with the valid string "abc".
Then we can insert another "abc" between "a" and "bc", resulting in "a" + "abc" + "bc" which is "aabcbc".
```

**Example 2:**

```
Input: "abcabcababcc"
Output: true
Explanation: 
"abcabcabc" is valid after consecutive insertings of "abc".
Then we can insert "abc" before the last letter, resulting in "abcabcab" + "abc" + "c" which is "abcabcababcc".
```

**Example 3:**

```
Input: "abccba"
Output: false
```

**Example 4:**

```
Input: "cababc"
Output: false
```

**Note:**

1. `1 <= S.length <= 20000`
2. `S[i]` is `'a'`, `'b'`, or `'c'`

```cpp
// Stack
bool isValid(string S) { // time: O(n); space: O(n)
    vector<char> st;
    for (char ch : S) {
        if (ch == 'c') {
            int n = st.size();
            if (n < 2 || st[n - 1] != 'b' || st[n - 2] != 'a') return false;
            st.pop_back(), st.pop_back();
        } else {
            st.push_back(ch);
        }
    }
    return st.empty();
}
```