LeetCode 1003 - Check If Word Is Valid After Substitutions

https://leetcode.com/problems/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'

X.
https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/discuss/248252/java-stack-solution-and-slight-different-ways
https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/discuss/247626/JavaPythonC%2B%2B-Stack-Solution-O(N)

Keep a stack, whenever meet 'c',
pop a and b at the end of stack.
Otherwise return false.

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

https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/discuss/247548/C%2B%2B-3-lines-search-and-remove

We search for "abc" substring and remove it from the string. If, in the end, the string is empty - return true.

bool isValid(string S) {
  for (auto i = S.find("abc"); i != string::npos; i = S.find("abc"))
    S.erase(i, 3);
  return S.empty();
}

Complexity Analysis

Runtime: O(n * n), where n is the number of characters. find is O(n + 3) and erase is O(n), and we repeat it n / 3 times.
Memory: O(n)

Solution 1, Brute Force

Brute force using replace will get accepted. Though it's not expected.

Time complexity O(N^2), space O(N^2) (depending on implementation).
Python

    def isValid(self, S):
        S2 = ""
        while S != S2:
            S, S2 = S.replace("abc", ""), S
        return S == ""