1003. Check If Word Is Valid After Substitutions

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.

Example 4:

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

 

Constraints:

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

Rust Solution

struct Solution;

impl Solution {
    fn is_valid(s: String) -> bool {
        let mut stack = vec![];
        for c in s.chars() {
            let n = stack.len();
            if n > 1 && c == 'c' && stack[n - 1] == 'b' && stack[n - 2] == 'a' {
                stack.pop();
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        stack.is_empty()
    }
}

#[test]
fn test() {
    let s = "aabcbc".to_string();
    let res = true;
    assert_eq!(Solution::is_valid(s), res);
    let s = "abcabcababcc".to_string();
    let res = true;
    assert_eq!(Solution::is_valid(s), res);
    let s = "abccba".to_string();
    let res = false;
    assert_eq!(Solution::is_valid(s), res);
    let s = "cababc".to_string();
    let res = false;
    assert_eq!(Solution::is_valid(s), res);
}

Having problems with this solution? Click here to submit an issue on github.