Scale Engineer

Check if a Parentheses String Can Be Valid

Med
#1927Time: O(n) - A single linear scan of the string is performed.Space: O(1) - Only a constant number of variables are used.1 company
Patterns
Greedy
Data structures
StringStack
Companies
ServiceNow

Prompt

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.

 

Example 1:

Input: s = "))()))", locked = "010100"
Output: true
Explanation: locked[1] == '1' and locked[3] == '1', so we cannot change s[1] or s[3].
We change s[0] and s[4] to '(' while leaving s[2] and s[5] unchanged to make s valid.

Example 2:

Input: s = "()()", locked = "0000"
Output: true
Explanation: We do not need to make any changes because s is already valid.

Example 3:

Input: s = ")", locked = "0"
Output: false
Explanation: locked permits us to change s[0]. 
Changing s[0] to either '(' or ')' will not make s valid.

Example 4:

Input: s = "(((())(((())", locked = "111111010111"
Output: true
Explanation: locked permits us to change s[6] and s[8]. 
We change s[6] and s[8] to ')' to make s valid.

 

Constraints:

  • n == s.length == locked.length
  • 1 <= n <= 105
  • s[i] is either '(' or ')'.
  • locked[i] is either '0' or '1'.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach refines the greedy strategy into a single pass. Instead of making a fixed greedy choice for unlocked characters, we track the possible range of balances at each prefix. We maintain a minOpen and maxOpen counter, representing the minimum and maximum possible balance (count('(') - count(')')) for the prefix processed so far. minOpen is achieved by treating all unlocked characters as ')', and maxOpen by treating them as '('.

Algorithm

  • First, check if n is odd. If so, return false.
  • Initialize two counters, minOpen and maxOpen, to 0. These will track the minimum and maximum possible balance of the current prefix.
  • Iterate through the string from i = 0 to n-1:
    • If locked[i] == '0' (unlocked character):
      • To get the minimum balance, we'd choose ')', so decrement minOpen.
      • To get the maximum balance, we'd choose '(', so increment maxOpen.
    • If locked[i] == '1' (fixed character):
      • If s[i] == '(', increment both minOpen and maxOpen.
      • If s[i] == ')', decrement both minOpen and maxOpen.
    • After updating the counters, perform two checks:
      • If maxOpen < 0, it means that even if we change all unlocked characters to '(', the balance becomes negative. This prefix can never be valid, so return false.
      • minOpen can become negative, which represents a choice of ')' that makes the balance negative. However, we can always choose '(' instead at an unlocked position to prevent this. So, we clamp minOpen at 0: minOpen = Math.max(0, minOpen).
  • After the loop, we need to check if a final balance of 0 is achievable. Since we've ensured that a non-negative balance is always possible for any prefix (by checking maxOpen >= 0 and clamping minOpen), we only need to check if a total balance of 0 is possible. This is true if and only if the final minOpen is 0. If minOpen > 0, it means even changing all unlocked characters to ')' results in a positive balance, so 0 cannot be reached.
  • Return minOpen == 0.

Walkthrough

The core idea is to maintain a range [minOpen, maxOpen] of possible net balances for the prefix s[0...i]. A net balance is the number of open parentheses minus the number of closed ones.

  • maxOpen: This is the balance if we greedily convert all unlocked characters in the prefix to '('. For any prefix to be part of a valid string, there must be some way to assign characters to make its balance non-negative. If maxOpen drops below zero, it means even the most optimistic assignment results in a negative balance, so we can immediately say it's impossible.

  • minOpen: This is the balance if we greedily convert all unlocked characters to ')'. This value can temporarily go negative. However, a negative minOpen doesn't mean failure, because it just represents one possible (pessimistic) assignment. We can always choose to flip an unlocked ')' to an '(' to increase the balance. Therefore, we clamp minOpen at 0 at each step (minOpen = Math.max(0, minOpen)). This essentially means we are only concerned with the lowest achievable non-negative balance.

After iterating through the entire string, we need to be able to form a string with a total balance of exactly 0. The final range of possible balances is [minOpen, maxOpen]. Since we've clamped minOpen to be non-negative, if the final minOpen is greater than 0, it means even the most ')'-heavy assignment results in a positive balance, making a balance of 0 impossible. If the final minOpen is 0, it means a balance of 0 is achievable. (We also know the final maxOpen will be even if n is even, and the range [minOpen, maxOpen] contains values with the same parity, so if 0 is in the range, it's reachable).

class Solution {    public boolean canBeValid(String s, String locked) {        int n = s.length();        if (n % 2 != 0) {            return false;        }         int minOpen = 0; // Minimum possible balance        int maxOpen = 0; // Maximum possible balance         for (int i = 0; i < n; i++) {            if (locked.charAt(i) == '1') {                if (s.charAt(i) == '(') {                    minOpen++;                    maxOpen++;                } else {                    minOpen--;                    maxOpen--;                }            } else { // unlocked                // We can choose ')' to decrease balance                minOpen--;                // We can choose '(' to increase balance                maxOpen++;            }             // If maxOpen is negative, it's impossible to have a valid prefix            if (maxOpen < 0) {                return false;            }                        // minOpen can be negative, but we can always use unlocked '(' to raise it.            // So, the effective minimum balance can't be less than 0.            minOpen = Math.max(0, minOpen);        }         // At the end, a balance of 0 must be achievable.        // Since we clamped minOpen at 0, this is equivalent to checking if minOpen is 0.        return minOpen == 0;    }}

Complexity

Time

O(n) - A single linear scan of the string is performed.

Space

O(1) - Only a constant number of variables are used.

Trade-offs

Pros

  • The most efficient solution, requiring only a single pass over the string.

  • Excellent performance with O(n) time and O(1) space complexity.

  • Provides an elegant way to handle the flexibility of unlocked characters by tracking a range of possibilities.

Cons

  • The logic, particularly the role of minOpen and why it's clamped at 0, can be more subtle and harder to grasp than the two-pass approach.

Solutions

class Solution {public  boolean canBeValid(String s, String locked) {    int n = s.length();    if (n % 2 == 1) {      return false;    }    int x = 0;    for (int i = 0; i < n; ++i) {      if (s.charAt(i) == '(' || locked.charAt(i) == '0') {        ++x;      } else if (x > 0) {        --x;      } else {        return false;      }    }    x = 0;    for (int i = n - 1; i >= 0; --i) {      if (s.charAt(i) == ')' || locked.charAt(i) == '0') {        ++x;      } else if (x > 0) {        --x;      } else {        return false;      }    }    return true;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem