Problem Description

You are given two strings of equal length n:

• s: a parentheses string containing only '(' and ')' characters
• locked: a binary string containing only '0' and '1' characters

The locked string determines which characters in s can be modified:

• If locked[i] = '1', the character s[i] is locked and cannot be changed
• If locked[i] = '0', the character s[i] is unlocked and can be changed to either '(' or ')'

A valid parentheses string must satisfy one of these conditions:

• It is exactly "()"
• It can be formed by concatenating two valid parentheses strings (like AB where both A and B are valid)
• It can be written as (A) where A is a valid parentheses string

Your task is to determine if it's possible to modify the unlocked characters in s to make it a valid parentheses string. Return true if it's possible, false otherwise.

For example:

• If s = "))()))" and locked = "010100", you can change s[1] to '(' and s[4] to '(' to get "()()()", which is valid, so return true
• If s = "()" and locked = "11", both characters are locked and the string is already valid, so return true
• If s = ")" and locked = "0", even though you can change the character, a single character cannot form a valid parentheses string, so return false

Intuition

First, we need to recognize that any valid parentheses string must have an even length. Each opening parenthesis needs a closing one to match with it, so if the length is odd, we can immediately return false.

The key insight is that we need to ensure two things:

1. Every '(' can find a matching ')' to its right
2. Every ')' can find a matching '(' to its left

For unlocked positions (where locked[i] = '0'), we have flexibility - we can choose either '(' or ')'. This means an unlocked position can serve as either type of parenthesis when needed.

Let's think about scanning from left to right. As we go through the string, we count how many unmatched '(' we have. When we see a '(' or an unlocked position, we can potentially use it as an opening parenthesis, so we increment our counter. When we see a ')', we need to match it with a previous '(' or unlocked position. If we have any available (counter > 0), we decrement the counter. If we don't have any available, it means this ')' cannot be matched, so we return false.

But wait - this only ensures that every ')' has a potential match to its left. What about ensuring every '(' has a match to its right?

That's where the second pass comes in. We do the same process but from right to left, treating ')' and unlocked positions as potentially available closing parentheses. This ensures that every '(' can find a matching ')' to its right.

If both passes succeed, we know that:

• All ')' characters can be matched with '(' or unlocked positions to their left
• All '(' characters can be matched with ')' or unlocked positions to their right
• The unlocked positions can be assigned appropriately to balance everything out

This greedy two-pass approach works because we're essentially checking if there's enough "flexibility" in both directions to create a valid matching.

Learn more about Stack and Greedy patterns.

Solution Approach

The implementation uses a greedy two-pass approach with a simple counter variable to track unmatched parentheses.

Step 1: Check for odd length

if n & 1:
    return False

We first check if the length is odd using bitwise AND (n & 1). If the last bit is 1, the number is odd, and we immediately return false since valid parentheses strings must have even length.

Step 2: First pass (left to right)

x = 0
for i in range(n):
    if s[i] == '(' or locked[i] == '0':
        x += 1
    elif x:
        x -= 1
    else:
        return False

We traverse from left to right with a counter x:

• When we encounter a '(' or an unlocked position (locked[i] == '0'), we increment x. These positions can potentially serve as opening parentheses.
• When we encounter a locked ')' (where s[i] == ')' and locked[i] == '1'), we need to match it:
  • If x > 0, we have available opening parentheses or unlocked positions to match with, so we decrement x
  • If x == 0, there's no way to match this ')', so we return false

Step 3: Second pass (right to left)

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

We traverse from right to left with the same logic but reversed:

• When we encounter a ')' or an unlocked position, we increment x. These can serve as closing parentheses.
• When we encounter a locked '(', we need to match it:
  • If x > 0, we have available closing parentheses or unlocked positions to match with, so we decrement x
  • If x == 0, there's no way to match this '(', so we return false

Step 4: Return true If both passes complete without returning false, it means all parentheses can be properly matched, and we return true.

The algorithm uses O(n) time complexity for the two passes through the string and O(1) space complexity as we only use a single counter variable. The greedy approach works because we're maximizing flexibility at each step - treating unlocked positions as wildcards that can be either type of parenthesis as needed.

Example Walkthrough

Let's walk through the example where s = "))()))" and locked = "010100".

Initial Setup:

• String length n = 6 (even, so we can proceed)
• We can modify positions 1 and 4 (where locked[i] = '0')

First Pass (Left to Right): We track available opening parentheses with counter x = 0:

First pass succeeds! Every locked ')' found a potential match.

Second Pass (Right to Left): We track available closing parentheses with counter x = 0:

Second pass also succeeds! No locked '(' needed matching (there were none).

Result: Both passes succeed, so we return true.

What actually happens: The unlocked positions at indices 1 and 4 can be changed to '(' to create "()()()", which is valid. Our algorithm detected this was possible without explicitly constructing the solution.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs two separate passes through the string:

• First pass: iterates from index 0 to n-1 (forward direction)
• Second pass: iterates from index n-1 to 0 (backward direction)

Each pass visits every character exactly once, performing constant-time operations (O(1)) at each position:

• Checking character values (s[i] and locked[i])
• Incrementing or decrementing the counter x
• Conditional checks

Total time = O(n) + O(n) = O(n), where n is the length of the input string.

Space Complexity: O(1)

The algorithm uses only a fixed amount of extra space:

• Variable n to store the string length
• Variable x as a counter (reused for both passes)
• Variable i for loop iteration

No additional data structures are created that scale with the input size. The space usage remains constant regardless of the input string length, resulting in O(1) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Thinking One Pass is Sufficient

The Mistake: A common misconception is that checking only from left to right would be sufficient. You might think that if you can match all parentheses going left to right, the string is valid.

Why It's Wrong: Consider s = "((" with locked = "00". A left-to-right pass would succeed (counting two potential opening parentheses), but the string cannot be made valid because there's no way to create matching closing parentheses.

The Solution: Both passes are essential:

• Left-to-right ensures no excess closing parentheses appear before their matching opening ones
• Right-to-left ensures no excess opening parentheses appear after their potential closing ones

Pitfall 2: Incorrect Handling of Unlocked Positions

The Mistake: Treating unlocked positions as fixed characters or trying to decide their type too early in the algorithm.

# WRONG approach - trying to fix unlocked positions prematurely
def canBeValid(self, s: str, locked: str) -> bool:
    # Convert unlocked positions to what we "think" they should be
    result = list(s)
    for i in range(len(s)):
        if locked[i] == '0':
            # Deciding too early what the character should be
            if i < len(s) // 2:
                result[i] = '('
            else:
                result[i] = ')'
    # Then check if valid...

Why It's Wrong: The optimal assignment of unlocked characters depends on the locked characters around them. For example, if you have many locked ')' at the beginning, you need unlocked positions there to become '(' regardless of their position.

The Solution: Treat unlocked positions as wildcards that can be either type. During the left-to-right pass, count them as potential opening parentheses. During the right-to-left pass, count them as potential closing parentheses. This maximizes flexibility.

Pitfall 3: Forgetting the Odd Length Check

The Mistake: Jumping straight into the validation logic without checking if the length is even.

# WRONG - missing length check
def canBeValid(self, s: str, locked: str) -> bool:
    open_count = 0
    for i in range(len(s)):
        # ... validation logic

Why It's Wrong: Valid parentheses strings must have equal numbers of opening and closing parentheses, which means the total length must be even. Without this check, you might waste computation on strings that can never be valid, or worse, incorrectly return true for odd-length strings.

The Solution: Always check if n & 1: return False at the beginning. This is an O(1) operation that can save unnecessary computation and ensure correctness.