Check if a parentheses string can be valid

String Stack Greedy

45.1% acceptance

Feb 25, 2026

2026

133

A parentheses string is a non-empty string consisting only of '(' and ')'. It is valid if any of the following conditions is true: It is (). It can be written as AB (A concatenated with B), where A and B are valid parentheses strings. It can be written as (A), where A is a valid parentheses string. You are given a parentheses string s and a string locked, both of length n. locked is a binary string consisting only of '0's and '1's. For each index i of locked, If locked[i] is '1', you cannot change s[i]. But if locked[i] is '0', you can change s[i] to either '(' or ')'. Return true if you can make s a valid parentheses string. Otherwise, return false.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn can_be_valid(s: String, locked: String) -> bool {
    let n = s.len();
    if n % 2 != 0 {
      return false;
    }
    let s: Vec<u8> = s.bytes().collect();
    let locked: Vec<u8> = locked.bytes().collect();

    // Greedy left-to-right: maintain range [lo, hi] of possible open counts
    let (mut lo, mut hi) = (0i32, 0i32);
    for i in 0..n {
      if locked[i] == b'0' {
        lo -= 1;
        hi += 1;
      } else if s[i] == b'(' {
        lo += 1;
        hi += 1;
      } else {
        lo -= 1;
        hi -= 1;
      }
      if hi < 0 {
        return false;
      }
      lo = lo.max(0);
    }
    lo == 0
  }
}