Check If Word Is Valid After Substitutions

Problem

Given a string s, determine if it is valid.

A string s is valid if, starting with an empty string t = "", you can transformtintos 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 ifs is avalid string, otherwise, return false.

Examples

Example 1

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

Example 2

Input: s = "abcabcababcc"
Output: true
Explanation:
"" -> "_abc_ " -> "abc _abc_ " -> "abcabc _abc_ " -> "abcabcab _abc_ c"
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 * 10^4
• s consists of letters 'a', 'b', and 'c'

Solution

Method 1 – Stack Simulation

Intuition

Since only the substring "abc" can be inserted, any valid string must be reducible to the empty string by repeatedly removing "abc" substrings. We can simulate this process using a stack.

Reasoning

By pushing characters onto a stack and checking if the top three characters form "abc", we can remove them whenever they appear. If the stack is empty at the end, the string is valid.

Approach

1. Initialize an empty stack.
2. Iterate through each character in the string:
   • Push the character onto the stack.
   • If the top three characters on the stack are 'a', 'b', 'c' (in order), pop them.
3. After processing all characters, return true if the stack is empty, otherwise false.

Edge cases:

• Strings shorter than 3 are never valid.
• Strings with leftover characters after all possible removals are invalid.

Code

C++

class Solution {
public:
    bool isValid(string s) {
        vector<char> stk;
        for (char c : s) {
            stk.push_back(c);
            if (stk.size() >= 3 && stk[stk.size()-3] == 'a' && stk[stk.size()-2] == 'b' && stk[stk.size()-1] == 'c') {
                stk.pop_back(); stk.pop_back(); stk.pop_back();
            }
        }
        return stk.empty();
    }
};

Go

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

Java

class Solution {
    public boolean isValid(String s) {
        StringBuilder stk = new StringBuilder();
        for (char c : s.toCharArray()) {
            stk.append(c);
            int n = stk.length();
            if (n >= 3 && stk.charAt(n-3) == 'a' && stk.charAt(n-2) == 'b' && stk.charAt(n-1) == 'c') {
                stk.setLength(n-3);
            }
        }
        return stk.length() == 0;
    }
}

Kotlin

class Solution {
    fun isValid(s: String): Boolean {
        val stk = StringBuilder()
        for (c in s) {
            stk.append(c)
            val n = stk.length
            if (n >= 3 && stk[n-3] == 'a' && stk[n-2] == 'b' && stk[n-1] == 'c') {
                stk.setLength(n-3)
            }
        }
        return stk.isEmpty()
    }
}

Python

class Solution:
    def is_valid(self, s: str) -> bool:
        stk = []
        for c in s:
            stk.append(c)
            if len(stk) >= 3 and stk[-3:] == ['a', 'b', 'c']:
                stk.pop(); stk.pop(); stk.pop()
        return not stk

Rust

impl Solution {
    pub fn is_valid(s: String) -> bool {
        let mut stk = Vec::new();
        for c in s.chars() {
            stk.push(c);
            let n = stk.len();
            if n >= 3 && stk[n-3] == 'a' && stk[n-2] == 'b' && stk[n-1] == 'c' {
                stk.truncate(n-3);
            }
        }
        stk.is_empty()
    }
}

Complexity

• ⏰ Time complexity: O(n), as each character is pushed and popped at most once.
• 🧺 Space complexity: O(n), as the stack can grow up to the length of the string.