Check if word is valid after substitutions

String Stack

61.1% acceptance

Feb 25, 2026

1081

473

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn is_valid(s: String) -> bool {
    let mut stack: Vec<u8> = Vec::new();
    for b in s.bytes() {
      if b == b'c' {
        if stack.len() < 2 || stack[stack.len()-1] != b'b' || stack[stack.len()-2] != b'a' {
          return false;
        }
        stack.pop(); stack.pop();
      } else {
        stack.push(b);
      }
    }
    stack.is_empty()
  }
}