Skip to content

1003. Check If Word Is Valid After Substitutions

Description

Given a string s, determine if it is valid.

A string s is valid if, starting with an empty string t = "", you can transform t into s after performing the following operation any number of times:

  • Insert string "abc" into any position in t. More formally, t becomes tleft + "abc" + tright, where t == tleft + tright. Note that tleft and tright may be empty.

Return true if s is a valid string, otherwise, return false.

 

Example 1:

Input: s = "aabcbc"
Output: true
Explanation:
"" -> "abc" -> "aabcbc"
Thus, "aabcbc" is valid.

Example 2:

Input: s = "abcabcababcc"
Output: true
Explanation:
"" -> "abc" -> "abcabc" -> "abcabcabc" -> "abcabcababcc"
Thus, "abcabcababcc" is valid.

Example 3:

Input: s = "abccba"
Output: false
Explanation: It is impossible to get "abccba" using the operation.

 

Constraints:

  • 1 <= s.length <= 2 * 104
  • s consists of letters 'a', 'b', and 'c'

Solutions

Solution 1: Stack

We observe the operations in the problem and find that each time a string \(\textit{"abc"}\) is inserted at any position in the string. Therefore, after each insertion operation, the length of the string increases by \(3\). If the string \(s\) is valid, its length must be a multiple of \(3\). Thus, we first check the length of the string \(s\). If it is not a multiple of \(3\), then \(s\) must be invalid, and we can directly return \(\textit{false}\).

Next, we traverse each character \(c\) in the string \(s\). We first push the character \(c\) onto the stack \(t\). If the length of the stack \(t\) is greater than or equal to \(3\), and the top three elements of the stack form the string \(\textit{"abc"}\), then we pop the top three elements from the stack. We then continue to traverse the next character in the string \(s\).

After the traversal, if the stack \(t\) is empty, it means the string \(s\) is valid, and we return \(\textit{true}\); otherwise, we return \(\textit{false}\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the string \(s\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 3:
            return False
        t = []
        for c in s:
            t.append(c)
            if ''.join(t[-3:]) == 'abc':
                t[-3:] = []
        return not t

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public boolean isValid(String s) {
        if (s.length() % 3 > 0) {
            return false;
        }
        StringBuilder t = new StringBuilder();
        for (char c : s.toCharArray()) {
            t.append(c);
            if (t.length() >= 3 && "abc".equals(t.substring(t.length() - 3))) {
                t.delete(t.length() - 3, t.length());
            }
        }
        return t.isEmpty();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 3) {
            return false;
        }
        string t;
        for (char c : s) {
            t.push_back(c);
            if (t.size() >= 3 && t.substr(t.size() - 3, 3) == "abc") {
                t.erase(t.end() - 3, t.end());
            }
        }
        return t.empty();
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func isValid(s string) bool {
    if len(s)%3 > 0 {
        return false
    }
    t := []byte{}
    for i := range s {
        t = append(t, s[i])
        if len(t) >= 3 && string(t[len(t)-3:]) == "abc" {
            t = t[:len(t)-3]
        }
    }
    return len(t) == 0
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function isValid(s: string): boolean {
    if (s.length % 3 !== 0) {
        return false;
    }
    const t: string[] = [];
    for (const c of s) {
        t.push(c);
        if (t.slice(-3).join('') === 'abc') {
            t.splice(-3);
        }
    }
    return t.length === 0;
}

Comments