LeetCode 2116 - Check if a Parentheses String Can Be Valid

This problem asks whether a given parentheses string can be transformed into a valid parentheses sequence under certain constraints. We are given two strings: - s, containing only '(' and ')' - locked, containing only '0' and '1' Both strings have the same length n.

leetcodemediumstringstackgreedy

LeetCode Problem 2116

Difficulty: 🟡 Medium
Topics: String, Stack, Greedy

Solution

Problem Understanding

This problem asks whether a given parentheses string can be transformed into a valid parentheses sequence under certain constraints.

We are given two strings:

  • s, containing only '(' and ')'
  • locked, containing only '0' and '1'

Both strings have the same length n.

At every index:

  • If locked[i] == '1', then s[i] is fixed and cannot be changed.
  • If locked[i] == '0', then s[i] is flexible and may become either '(' or ')'.

The goal is to determine whether we can assign values to all unlocked positions so that the final string becomes a valid parentheses string.

A valid parentheses string must satisfy two important conditions:

  1. The total number of opening and closing parentheses must be equal.
  2. At no point while scanning from left to right should closing parentheses exceed opening parentheses.

For example:

  • "()" is valid.
  • "(())" is valid.
  • "(()" is invalid because one opening parenthesis is unmatched.
  • ")(" is invalid because the string starts with a closing parenthesis.

The constraints are important:

  • n can be as large as 10^5
  • This immediately rules out exponential or heavy backtracking solutions.
  • We need an algorithm close to O(n) time.

There are several important edge cases:

  • If the length is odd, the answer is automatically false, because a valid parentheses string must contain equal numbers of '(' and ')'.
  • Strings with many locked closing parentheses near the beginning can fail immediately.
  • Strings with many locked opening parentheses near the end can also fail.
  • Fully unlocked strings are always solvable when the length is even.
  • A naive greedy strategy that only scans left to right is insufficient because we must also ensure enough closing parentheses exist later in the string.

The core challenge is balancing flexibility while respecting locked positions.

Approaches

Brute Force Approach

The brute force approach tries every possible assignment for unlocked positions.

Suppose there are k unlocked indices. Each unlocked character can independently become either '(' or ')', so there are:

$2^k$

possible strings to test.

For each generated string, we can validate whether it forms a legal parentheses sequence using a standard stack or counter method.

This approach is correct because it explores every possible configuration. If any valid configuration exists, brute force will eventually find it.

However, this is computationally infeasible.

In the worst case:

  • k = n
  • n = 10^5

This leads to exponential complexity, which is impossible to execute within time limits.

Optimal Greedy Approach

The key observation is that we do not need to explicitly construct the final string.

Instead, we only need to determine whether a valid assignment is possible.

A valid parentheses string has two directional requirements:

  1. While scanning left to right, we must never have too many ')'.
  2. While scanning right to left, we must never have too many '('.

Unlocked characters are flexible and can temporarily compensate for whichever parenthesis type we currently need.

This leads to a greedy validation strategy using two passes:

  • Left-to-right pass ensures enough opening parentheses exist.
  • Right-to-left pass ensures enough closing parentheses exist.

If both passes succeed, then a valid assignment exists.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^k × n) O(n) Tries every assignment for unlocked positions
Optimal O(n) O(1) Uses two greedy scans to validate feasibility

Algorithm Walkthrough

Step 1: Check String Length

A valid parentheses string must contain equal numbers of opening and closing parentheses.

Therefore, the total length must be even.

If n is odd, immediately return false.

Step 2: Left-to-Right Validation

We scan from left to right and track how many opening parentheses are potentially available.

We maintain a counter called balance.

At each index:

  • If the character is unlocked (locked[i] == '0'), we treat it as potentially '('.
  • If the character is locked and already '(', it contributes positively.
  • Otherwise, it is a locked ')', which consumes one available opening parenthesis.

The update rules become:

  • Flexible or '(' → balance += 1
  • Locked ')' → balance -= 1

If balance ever becomes negative, then there are too many closing parentheses before enough openings exist.

In that case, return false.

Step 3: Right-to-Left Validation

Now we perform the symmetric check from right to left.

This time we ensure enough closing parentheses can exist.

Again maintain a counter called balance.

At each index:

  • If the character is unlocked, treat it as potentially ')'.
  • If the character is locked and already ')', it contributes positively.
  • Otherwise, it is a locked '(', which consumes one available closing parenthesis.

The update rules become:

  • Flexible or ')' → balance += 1
  • Locked '(' → balance -= 1

If balance becomes negative, there are too many opening parentheses that cannot be matched later.

Return false.

Step 4: Return True

If both directional checks succeed, then a valid assignment exists.

Return true.

Why it works

The algorithm maintains a feasibility invariant.

During the left-to-right scan, we guarantee that every prefix can potentially contain enough opening parentheses to balance all encountered closing parentheses.

During the right-to-left scan, we guarantee that every suffix can potentially contain enough closing parentheses to balance all encountered opening parentheses.

If both conditions hold simultaneously, then there exists at least one assignment of flexible positions that satisfies the rules of a valid parentheses string.

Python Solution

class Solution:
    def canBeValid(self, s: str, locked: str) -> bool:
        n = len(s)

        # Valid parentheses strings must have even length
        if n % 2 == 1:
            return False

        # Left-to-right pass
        balance = 0

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

            if balance < 0:
                return False

        # Right-to-left pass
        balance = 0

        for i in range(n - 1, -1, -1):
            if locked[i] == '0' or s[i] == ')':
                balance += 1
            else:
                balance -= 1

            if balance < 0:
                return False

        return True

The implementation begins with the parity check because odd-length strings can never become valid.

The first loop performs the left-to-right validation. Flexible characters are optimistically treated as '(' because opening parentheses help prevent premature imbalance caused by closing parentheses.

Whenever a locked ')' appears, the balance decreases because it must consume a previously available opening parenthesis.

If the balance becomes negative, then no assignment can repair the invalid prefix.

The second loop mirrors the logic in reverse. Flexible positions are now treated as ')' because we want to ensure enough closing parentheses exist for all opening parentheses.

If either scan fails, the function immediately returns False.

If both scans complete successfully, the string can be transformed into a valid parentheses sequence.

Go Solution

func canBeValid(s string, locked string) bool {
	n := len(s)

	// Valid parentheses strings must have even length
	if n%2 == 1 {
		return false
	}

	// Left-to-right pass
	balance := 0

	for i := 0; i < n; i++ {
		if locked[i] == '0' || s[i] == '(' {
			balance++
		} else {
			balance--
		}

		if balance < 0 {
			return false
		}
	}

	// Right-to-left pass
	balance = 0

	for i := n - 1; i >= 0; i-- {
		if locked[i] == '0' || s[i] == ')' {
			balance++
		} else {
			balance--
		}

		if balance < 0 {
			return false
		}
	}

	return true
}

The Go implementation follows the exact same logic as the Python version.

Strings in Go are byte-indexable, so accessing s[i] and locked[i] is efficient because the input contains only ASCII characters.

No additional data structures are needed, so the implementation maintains constant auxiliary space usage.

Worked Examples

Example 1

s = "))()))"
locked = "010100"

Left-to-Right Pass

Index s[i] locked[i] Action Balance
0 ) 0 flexible, treat as '(' 1
1 ) 1 locked ')' 0
2 ( 0 flexible, treat as '(' 1
3 ) 1 locked ')' 0
4 ) 0 flexible, treat as '(' 1
5 ) 0 flexible, treat as '(' 2

The pass succeeds.

Right-to-Left Pass

Index s[i] locked[i] Action Balance
5 ) 0 flexible, treat as ')' 1
4 ) 0 flexible, treat as ')' 2
3 ) 1 locked ')' 3
2 ( 0 flexible, treat as ')' 4
1 ) 1 locked ')' 5
0 ) 0 flexible, treat as ')' 6

Both passes succeed, so the answer is true.

Example 2

s = "()()"
locked = "0000"

All positions are flexible.

Since the length is even and flexibility exists everywhere, both scans succeed easily.

Result: true.

Example 3

s = ")"
locked = "0"

The length is odd.

A valid parentheses string cannot have odd length.

Result: false.

Example 4

s = "(((())(((())"
locked = "111111010111"

The flexible positions allow enough adjustments to create matching closing parentheses.

Both directional scans remain non-negative.

Result: true.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Two linear scans through the string
Space O(1) Only a few integer counters are used

The algorithm processes each character at most twice, once during the forward scan and once during the backward scan.

No auxiliary arrays, stacks, or recursion are required, so the extra memory usage remains constant regardless of input size.

Test Cases

sol = Solution()

# Provided examples
assert sol.canBeValid("))()))", "010100") == True  # flexible positions can fix string
assert sol.canBeValid("()()", "0000") == True  # already valid with all flexible
assert sol.canBeValid(")", "0") == False  # odd length
assert sol.canBeValid("(((())(((())", "111111010111") == True  # selective fixes work

# Basic valid cases
assert sol.canBeValid("()", "11") == True  # already valid locked string
assert sol.canBeValid("()", "00") == True  # fully flexible

# Basic invalid cases
assert sol.canBeValid("((", "11") == False  # cannot close openings
assert sol.canBeValid("))", "11") == False  # cannot open before closings

# Odd length cases
assert sol.canBeValid("(()", "000") == False  # odd length impossible
assert sol.canBeValid("(", "0") == False  # single character

# Fully flexible cases
assert sol.canBeValid("))))", "0000") == True  # can convert to valid
assert sol.canBeValid("((((", "0000") == True  # can convert to valid

# Prefix imbalance cases
assert sol.canBeValid(")(", "10") == False  # locked invalid prefix
assert sol.canBeValid("))((", "1100") == False  # impossible prefix structure

# Suffix imbalance cases
assert sol.canBeValid("(()(", "1111") == False  # unmatched openings at end

# Mixed locked and unlocked
assert sol.canBeValid("())(", "1010") == False  # cannot fully repair
assert sol.canBeValid("())(", "1001") == True  # flexible middle repairs structure

# Large balanced structure
assert sol.canBeValid("(((())))", "11111111") == True  # fully locked valid

# Edge cases with alternating flexibility
assert sol.canBeValid(")()(", "0101") == True  # flexibility enables balancing

Test Summary

Test Why
"))()))" Verifies mixed locked and unlocked repair
"()()" Confirms already-valid flexible input
")" Validates odd-length rejection
"(((())(((())" Tests complex balancing
"((" Detects unmatched openings
"))" Detects unmatched closings
"(()" Confirms odd lengths always fail
"(((( " with all unlocked Ensures flexibility can repair structure
")(" Tests impossible prefix imbalance
"(()(" Tests impossible suffix imbalance
Mixed repairable cases Verifies greedy correctness
Fully locked valid input Ensures stable valid strings pass

Edge Cases

Odd Length Strings

A valid parentheses string must contain equal numbers of opening and closing parentheses. Therefore, its total length must always be even.

This is a common source of bugs because developers may begin complex validation logic unnecessarily.

The implementation handles this immediately with:

if n % 2 == 1:
    return False

This prevents wasted computation and guarantees correctness.

Too Many Closing Parentheses Early

Consider:

s = "))(("
locked = "1100"

The first two characters are locked closing parentheses.

Even though later positions are flexible, no valid assignment can fix the invalid prefix because a valid parentheses string can never start with unmatched ')'.

The left-to-right scan catches this when the balance becomes negative.

Too Many Opening Parentheses Late

Consider:

s = "(()("
locked = "1111"

The prefix structure appears valid during a forward scan, but the final opening parenthesis can never be matched.

A naive single-pass solution would incorrectly accept this case.

The reverse scan prevents this bug by ensuring enough closing parentheses exist in every suffix.

Fully Flexible Strings

Consider:

s = "))))"
locked = "0000"

Although the original string looks invalid, every position is mutable.

The algorithm correctly recognizes that flexible positions can be reassigned to form "()()" or "(())".

This demonstrates why we must reason about possibility rather than the current literal characters.