#2116

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Check if a Parentheses String Can Be Valid

Determine if a parentheses string can be transformed into a valid sequence considering locked positions using stack logic.

string stack greedy

Problem Statement

You are given a string s consisting only of '(' and ')' characters and a binary string locked of the same length. Each '1' in locked indicates that the corresponding character in s cannot be changed, while '0' means you can change it to either '(' or ')'. Determine if it is possible to modify s at unlocked positions to form a valid parentheses string.

A string of parentheses is valid if every opening '(' has a corresponding closing ')' and the order is correct. Return true if s can be transformed into a valid string under the locked constraints, otherwise return false. Keep in mind that strings with odd length can never be valid.

Examples

Example 1

Input: s = "))()))", locked = "010100"

Output: true

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

We do not need to make any changes because s is already valid.

Example 3

Input: s = ")", locked = "0"

Output: false

locked permits us to change s[0]. Changing s[0] to either '(' or ')' will not make s valid.

Constraints

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

Solution Approach

Two-Pass Greedy Check

Traverse the string left-to-right, counting the minimum and maximum possible open parentheses at each position, adjusting for locked and unlocked characters. Then traverse right-to-left to ensure closing balance. If at any point the minimum possible opens drop below zero, return false.

Stack-Based Simulation

Simulate the string using a virtual stack where unlocked characters can be chosen to balance parentheses. Push for '(' and pop for ')', treating unlocked positions as flexible to maintain stack non-negativity. If the stack empties correctly at the end, the string can be valid.

Quick Odd Length Rejection

Immediately return false if the string length is odd, as no valid parentheses sequence can exist. This early exit handles a common failure mode before running more detailed simulations.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) since each character is processed in both left-to-right and right-to-left passes. Space complexity is O(1) using counters instead of an actual stack.

What Interviewers Usually Probe

Can you check if the string length is odd as a quick fail case?
How would you track balance considering locked and unlocked positions efficiently?
Can you simulate stack behavior without actually using extra space?

Common Pitfalls or Variants

Common pitfalls

Assuming all unlocked characters can be freely chosen without considering positions of locked characters.
Ignoring the need to check balance in both directions, which can miss invalid strings ending with extra '('.
Forgetting that strings of odd length can never be valid.

Follow-up variants

Allowing multiple types of brackets like '[]' and '{}' with the same locked rules.
Counting the minimum changes needed to make the string valid instead of just returning true/false.
Checking validity when some locked positions allow only a subset of possible parentheses types.

FAQ

Can a string with odd length ever be valid in 'Check if a Parentheses String Can Be Valid'?

No, any string with an odd length cannot form a valid parentheses sequence regardless of changes allowed.

What does locked = '1' signify in this problem?

A '1' in locked indicates that the corresponding character in s cannot be changed and must remain as is.

How do we handle unlocked characters optimally?

Use them flexibly to balance parentheses in both left-to-right and right-to-left passes, adjusting minimum and maximum counts.

Is a real stack necessary for this solution?

No, counters simulating stack depth suffice for O(1) space while maintaining balance tracking.

Why is a two-pass approach recommended?

Because left-to-right ensures opening balance, and right-to-left ensures closing balance, covering all locked constraints.

terminal

Solution

Solution 1: Greedy + Two Passes

We observe that a string of odd length cannot be a valid parentheses string because there will always be one unmatched parenthesis. Therefore, if the length of the string $s$ is odd, return $\textit{false}$ immediately.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

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

Continue Practicing

#2030 smallest k length subsequence with occurrences of a letter #1963 minimum number of swaps to make the string balanced #2375 construct smallest number from di string