> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Check if a Parentheses String Can Be Valid

> Tested Python solution for LeetCode 2116 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 2116, [Medium](/catalog/medium). Topics: [String](/catalog/topics/string), [Stack](/catalog/topics/stack), [Greedy](/catalog/topics/greedy), Bracket Sequences. [View on LeetCode](https://leetcode.com/problems/check-if-a-parentheses-string-can-be-valid/description/).

Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2116   # by problem number
lcpy gen -s check_if_a_parentheses_string_can_be_valid   # by problem name
```

## 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`.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2021/11/06/eg1.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.
```

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

```
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.
```

```
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 <= 10^5`
* `s[i]` is either `'('` or `')'`.
* `locked[i]` is either `'0'` or `'1'`.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/check_if_a_parentheses_string_can_be_valid/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/check_if_a_parentheses_string_can_be_valid/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n)
    # Space: O(1)
    def can_be_valid(self, s: str, locked: str) -> bool:
        if len(s) % 2:
            return False
        low = high = 0
        for char, lock in zip(s, locked, strict=True):
            if lock == "0":
                low -= 1
                high += 1
            elif char == "(":
                low += 1
                high += 1
            else:
                low -= 1
                high -= 1
            if high < 0:
                return False
            low = max(low, 0)
        return low == 0
```

## Complexity

| Time | Space |
| - | - |
| O(n) | O(1) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.