# Check if a Parentheses String Can Be Valid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/check-if-a-parentheses-string-can-be-valid)
Canonical: https://scaleengineer.com/dsa/problems/check-if-a-parentheses-string-can-be-valid
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String, Stack
**Companies:** [ServiceNow](https://scaleengineer.com/companies/servicenow)
---
## Problem
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:**

![](https://assets.glich.co/dsa/check-if-a-parentheses-string-can-be-valid/image0.png) 

**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
## Dynamic Programming
This approach uses dynamic programming to solve the problem. We build a table `dp[i][j]` which stores whether it's possible for the prefix of the string of length `i` to have a balance of `j`, where balance is the number of open brackets minus the number of closed brackets. By iterating through the string and considering the locked/unlocked status of each character, we can fill this table and find if a final balance of 0 is achievable for the whole string.
**Time:** O(n^2) - We have nested loops, one for the string length `i` (up to `n`) and one for the balance `j` (up to `n`). · **Space:** O(n^2) - We use a 2D DP table of size `(n+1) x (n+1)`.
**Pros:** It's a systematic approach that correctly explores all valid possibilities.; The logic is a direct extension of the standard parenthesis validation problem.
**Cons:** The time complexity of O(n^2) is too slow for the given constraints (n up to 10^5), leading to a 'Time Limit Exceeded' error.; The space complexity of O(n^2) is also very high and may cause memory issues for large n.
### Explanation
The state of our DP can be defined as `dp[i][j]`, representing a boolean value indicating whether the prefix `s[0...i-1]` can be transformed into a valid partial parenthesis string with a balance of `j`. A balance of `j` means there are `j` more open parentheses than closed ones. For a prefix to be valid, its balance must never be negative.

We iterate through the string from left to right, character by character. For each character `s[i-1]`, we compute the possible balances for the prefix of length `i` based on the possible balances of the prefix of length `i-1`.

- If `s[i-1]` is fixed (i.e., `locked[i-1] == '1'`), its contribution to the balance is fixed. An opening bracket `'('` increases the balance by 1, and a closing bracket `')'` decreases it by 1.
- If `s[i-1]` is not fixed (i.e., `locked[i-1] == '0'`), we have a choice. We can change it to `'('` (increasing balance by 1) or `')'` (decreasing balance by 1). Thus, a state `dp[i-1][k]` can potentially lead to two new states: `dp[i][k+1]` and `dp[i][k-1]`.

The final answer is `dp[n][0]`, which tells us if the entire string can be formed with a total balance of zero.

```java
class Solution {
    public boolean canBeValid(String s, String locked) {
        int n = s.length();
        if (n % 2 != 0) {
            return false;
        }

        boolean[][] dp = new boolean[n + 1][n + 1];
        dp[0][0] = true;

        for (int i = 1; i <= n; i++) {
            char ch = s.charAt(i - 1);
            char lock = locked.charAt(i - 1);

            for (int j = 0; j <= i; j++) {
                if (lock == '0') {
                    // Can be '('
                    if (j > 0 && dp[i - 1][j - 1]) {
                        dp[i][j] = true;
                    }
                    // Can be ')'
                    if (j + 1 <= n && dp[i - 1][j + 1]) {
                        dp[i][j] = true;
                    }
                } else {
                    if (ch == '(') {
                        if (j > 0 && dp[i - 1][j - 1]) {
                            dp[i][j] = true;
                        }
                    } else { // ch == ')'
                        if (j + 1 <= n && dp[i - 1][j + 1]) {
                            dp[i][j] = true;
                        }
                    }
                }
            }
        }

        return dp[n][0];
    }
}
```
### Algorithm
- First, perform a basic check: if the length of the string `n` is odd, it's impossible to form a valid parenthesis string, so return `false`.
- Create a 2D boolean array `dp` of size `(n + 1) x (n + 1)`. `dp[i][j]` will be `true` if the prefix of `s` of length `i` can be made valid with a balance of `j` (where balance is `count('(') - count(')')`).
- Initialize `dp[0][0] = true`, as an empty string has a balance of 0.
- Iterate from `i = 1` to `n` (for each character in `s`) and for each `i`, iterate `j` from `0` to `i` (for each possible balance).
- For each `(i, j)` pair, determine if `dp[i][j]` can be `true` based on the character `s[i-1]`, `locked[i-1]`, and the previous row `dp[i-1]`:
  - If `locked[i-1]` is `'1'` (character is fixed):
    - If `s[i-1]` is `'('`, `dp[i][j]` can be true only if `dp[i-1][j-1]` was true (and `j > 0`).
    - If `s[i-1]` is `')'`, `dp[i][j]` can be true only if `dp[i-1][j+1]` was true.
  - If `locked[i-1]` is `'0'` (character can be changed):
    - It can be `'('`: `dp[i][j]` can be true if `dp[i-1][j-1]` was true (and `j > 0`).
    - It can be `')'`: `dp[i][j]` can be true if `dp[i-1][j+1]` was true.
- After filling the table, the answer is `dp[n][0]`. This checks if the entire string can have a final balance of 0.

## Two-Pass Greedy Approach
A much more efficient approach is to use a greedy strategy. The validity of a parenthesis string depends on two main properties: the total count of open and close brackets being equal, and the balance never being negative during a left-to-right scan. We can check if these conditions can be met using two passes.

The first pass is from left to right. We greedily assume all unlocked characters are `'('` to give us the best chance of keeping the balance non-negative. If the balance still drops below zero, no assignment can work.

The second pass is from right to left. We greedily assume all unlocked characters are `')'` to give us the best chance of satisfying the equivalent suffix condition (number of `')'` must be at least the number of `'('` in any suffix). If this also succeeds, a valid string can be formed.
**Time:** O(n) - We perform two linear passes through the string. · **Space:** O(1) - We only use a few integer variables to keep track of the balance.
**Pros:** Highly efficient with O(n) time complexity.; Constant space complexity, O(1).; The implementation is simple and concise.
**Cons:** The logic requires two separate passes over the input string.; The proof of correctness is not immediately obvious, as it relies on the fact that if optimistic choices in both directions are possible, a valid assignment exists.
### Explanation
This greedy approach is based on checking the two fundamental properties of a valid parenthesis string from two different perspectives.

1.  **Prefix Validity (Left-to-Right Scan):** For any prefix of a valid string, the number of opening brackets must be greater than or equal to the number of closing brackets. To check if this is achievable, we make the most optimistic choices. When scanning from left to right, an opening bracket is always helpful for maintaining a non-negative balance. Therefore, we treat every unlocked character as an `'('`. If, even with this greedy choice, the balance `count('(') - count(')')` drops below zero at any point, it's impossible to satisfy the condition, and we can immediately conclude the string cannot be made valid.

2.  **Suffix Validity (Right-to-Left Scan):** An equivalent property is that for any suffix, the number of closing brackets must be greater than or equal to the number of opening brackets. We can check this with a scan from right to left. Here, a closing bracket is the helpful choice. So, we treat every unlocked character as a `')'`. If the balance `count(')') - count('(')` drops below zero during this reverse scan, the string cannot be made valid.

If the string's length is even and it passes both these greedy checks, it can be proven that a valid assignment for the unlocked characters exists.

```java
class Solution {
    public boolean canBeValid(String s, String locked) {
        int n = s.length();
        if (n % 2 != 0) {
            return false;
        }

        // Left-to-right pass: Check for prefix validity
        // Greedily treat '0' as '('
        int balance = 0;
        for (int i = 0; i < n; i++) {
            if (locked.charAt(i) == '0' || s.charAt(i) == '(') {
                balance++;
            } else {
                balance--;
            }
            if (balance < 0) {
                return false;
            }
        }

        // Right-to-left pass: Check for suffix validity
        // Greedily treat '0' as ')'
        balance = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (locked.charAt(i) == '0' || s.charAt(i) == ')') {
                balance++;
            } else {
                balance--;
            }
            if (balance < 0) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
- First, check if `n` is odd. If so, return `false`.
- **Left-to-Right Pass:** This pass ensures that we can always satisfy the prefix condition (`count('(') >= count(')')`).
  - Initialize a `balance` counter to 0.
  - Iterate through the string from `i = 0` to `n-1`.
  - To be as optimistic as possible about satisfying the prefix condition, we treat every unlocked character (`locked[i] == '0'`) as an opening parenthesis `'('`.
  - If `s[i]` is a fixed `')'`, decrement `balance`. Otherwise (if it's a fixed `'('` or an unlocked character), increment `balance`.
  - If `balance` ever drops below 0, it means we have an excess of closing brackets in a prefix that cannot be fixed. Return `false`.
- **Right-to-Left Pass:** This pass ensures that we can satisfy the suffix condition (`count(')') >= count('(')` for any suffix).
  - Reset the `balance` counter to 0.
  - Iterate through the string from `i = n-1` down to `0`.
  - To be optimistic for this condition, we treat every unlocked character as a closing parenthesis `')'`.
  - If `s[i]` is a fixed `'('`, decrement `balance`. Otherwise (if it's a fixed `')'` or an unlocked character), increment `balance`.
  - If `balance` ever drops below 0, it means we have an excess of opening brackets in a suffix that cannot be fixed. Return `false`.
- If both passes complete without returning `false`, it is possible to make the string valid. Return `true`.

## Single-Pass Approach with Balance Range
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 `'('`.
**Time:** O(n) - A single linear scan of the string is performed. · **Space:** O(1) - Only a constant number of variables are used.
**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.
### Explanation
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).

```java
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;
    }
}
```
### 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`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool canBeValid(string s, string locked) {
    int n = s.size();
    if (n & 1) {
      return false;
    }
    int x = 0;
    for (int i = 0; i < n; ++i) {
      if (s[i] == '(' || locked[i] == '0') {
        ++x;
      } else if (x) {
        --x;
      } else {
        return false;
      }
    }
    x = 0;
    for (int i = n - 1; i >= 0; --i) {
      if (s[i] == ')' || locked[i] == '0') {
        ++x;
      } else if (x) {
        --x;
      } else {
        return false;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def canBeValid(self, s: str, locked: str) -> bool: n = len(s) if n & 1: return False x = 0 for i in range(n): if s[i] == '(' or locked[i] == '0': x += 1 elif x: x -= 1 else: return False x = 0 for i in range(n - 1, - 1, - 1): if s[i] == ')' or locked[i] == '0': x += 1 elif x: x -= 1 else: return False return True

```