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 <= S.length <= 20000
S[i] is ‘a’, ‘b’, or ‘c’

Repeated String Substitutions or Substring Removal

One intuitive solution is to continuously remove the substring “abc” until we can’t. If the result string is empty “”, then it is a Valid word After Substitutions. This can be implemented using the Recursion:

1
2
3
4
5
6
7
8
9

class Solution {
public:
    bool isValid(string S) {        
        if (S.empty()) return true;
        auto idx = S.find("abc");
        if (idx == string::npos) return false;
        return isValid(S.replace(idx, 3, ""));
    }
};

class Solution {
public:
    bool isValid(string S) {        
        if (S.empty()) return true;
        auto idx = S.find("abc");
        if (idx == string::npos) return false;
        return isValid(S.replace(idx, 3, ""));
    }
};

We use the C++ string::replace function to remove the substring by replacing it as empty string “”. The first parameter is the start of the replacement, and the next parameter is the length you would like it to be replaced. And the third parameter is the new substring to substitute.

Alternatively, we can iteratively remove the substrings.

1
2
3
4
5
6
7
8
9

class Solution {
public:
    bool isValid(string S) {        
        while (S.find("abc") != string::npos) {
            S = S.replace(S.find("abc"), 3, "");
        }
        return S.empty();
    }
};

class Solution {
public:
    bool isValid(string S) {        
        while (S.find("abc") != string::npos) {
            S = S.replace(S.find("abc"), 3, "");
        }
        return S.empty();
    }
};

However the above C++ implementation will call the string.find() method twice, which is not efficient. We might need to cache it.

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    bool isValid(string S) {        
        int idx = S.find("abc");
        while (idx != string::npos) {
            S = S.replace(idx, 3, "");
            idx = S.find("abc");
        }
        return S.empty();
    }
};

class Solution {
public:
    bool isValid(string S) {        
        int idx = S.find("abc");
        while (idx != string::npos) {
            S = S.replace(idx, 3, "");
            idx = S.find("abc");
        }
        return S.empty();
    }
};

As finding a substring requires O(N) time, the entire algorithm complexity is O(N^N) which is exponential. There is also overhead in substring substitution (removal) and re-constructing a string (copy).

Using Stack

We can use a stack to store the process of concatenating the substrings. If it is “a”, we push it to the stack (starting a new nested substring), if it is “b”, we need to check the top of the stack. If the stack is empty, thus it is invalid. If the top of the stack is not “a”, then it is also invalid as it can’t be substring “abc”. Otherwise, we push “ab” substring back to the stack.

Similarly, if “c” is met, we need to check if the top of the stack is “ab” but we do not need to push “abc” back to the stack. The process continues until the string is all processed, and at this moment, the stack should be empty which indicates the original string is a valid string after substitution of substrings “abc”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    bool isValid(string S) {
        stack<string> st;
        for (const auto &n: S) {
            if (n == 'a') {
                st.push("a");
            } else if (n == 'b') {
                if (st.empty()) return false;
                auto p = st.top();
                st.pop();
                if (p != "a") return false;
                st.push("ab");
            } else {
                if (st.empty()) return false;
                auto p = st.top();
                st.pop();
                if (p != "ab") return false;
            }
        }
        return st.empty();
    }
};

class Solution {
public:
    bool isValid(string S) {
        stack<string> st;
        for (const auto &n: S) {
            if (n == 'a') {
                st.push("a");
            } else if (n == 'b') {
                if (st.empty()) return false;
                auto p = st.top();
                st.pop();
                if (p != "a") return false;
                st.push("ab");
            } else {
                if (st.empty()) return false;
                auto p = st.top();
                st.pop();
                if (p != "ab") return false;
            }
        }
        return st.empty();
    }
};

In fact, we just need to check the last character instead of comparison of the entire substring. The following implementation is slightly faster.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    bool isValid(string S) {
        stack<string> st;
        for (const auto &n: S) {
            if (n == 'a') {
                st.push("a");
            } else if (n == 'b') {
                if (st.empty()) return false;
                auto p = st.top();
                st.pop();
                if (p.back() != 'a') return false;
                st.push("ab");
            } else {
                if (st.empty()) return false;
                auto p = st.top();
                st.pop();
                if (p.back() != 'b') return false;
            }
        }
        return st.empty();
    }
};

class Solution {
public:
    bool isValid(string S) {
        stack<string> st;
        for (const auto &n: S) {
            if (n == 'a') {
                st.push("a");
            } else if (n == 'b') {
                if (st.empty()) return false;
                auto p = st.top();
                st.pop();
                if (p.back() != 'a') return false;
                st.push("ab");
            } else {
                if (st.empty()) return false;
                auto p = st.top();
                st.pop();
                if (p.back() != 'b') return false;
            }
        }
        return st.empty();
    }
};

The algorithm of using a stack to check the valid word after substitution (as above) requires a O(N) linear space i.e. stack where N is the number of substrings “abc” in the origin string, which can be approximately to M/3 (in the worst case) where M is the length of the string. One special test case is “aaaaaaaaaaaaaaaaaaaaaaaaaa….bcbcbcbcbc…..”

The time complexity is O(N) where N is the length of the string.

–EOF (The Ultimate Computing & Technology Blog) —