We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check if a Parentheses String Can Be Valid

Number: 2221

Difficulty: Medium

Paid? No

Companies: Google, Amazon

Problem Description

Given a parentheses string s and a binary string locked of the same length, determine if it is possible to make s a valid parentheses string by changing the characters in s at indices where locked[i] is '0'. A valid parentheses string is one that satisfies traditional parentheses matching rules.

Key Insights

  • We can replace any character at an unlocked index (where locked[i] is '0') to either '(' or ')'.
  • A valid parentheses string requires that at every prefix there are at least as many '(' as ')'.
  • We can perform two passes:
    • Left-to-right pass assuming each unlocked character is '(' to maximize the opening count.
    • Right-to-left pass assuming each unlocked character is ')' to maximize the closing count.
  • If both passes verify that a valid configuration is achievable, then the string can be made valid.

Space and Time Complexity

Time Complexity: O(n) because we iterate through the string twice. Space Complexity: O(1) since we use a few integer counters.

Solution

We solve the problem with a greedy two-pass approach. In the first pass (left-to-right), we treat every unlocked character as an opening parenthesis '(' to ensure that the net balance (openings minus closings) never falls negative. In the second pass (right-to-left), we treat every unlocked character as a closing parenthesis ')' to ensure that the reverse net balance never falls negative. Using these two simulation passes, we can determine if there exists a valid replacement for all unlocked positions such that the string becomes a valid parentheses string.

Code Solutions

# Python solution with line-by-line comments

def canBeValid(s: str, locked: str) -> bool:
    n = len(s)
    # If the length of s is odd, it's impossible to balance parentheses.
    if n % 2 != 0:
        return False

    balance = 0
    # Left-to-right pass: treat unlocked positions as '(' to maximize openings.
    for i in range(n):
        # If the position is locked, check the character.
        if locked[i] == '1':
            if s[i] == '(':
                balance += 1
            else:  # s[i] == ')'
                balance -= 1
        else:
            # Unlocked position: treat as '(' to compensate for potential deficit.
            balance += 1

        # If then balance goes negative, there is no way to balance.
        if balance < 0:
            return False

    balance = 0
    # Right-to-left pass: treat unlocked positions as ')' to maximize closings.
    for i in range(n - 1, -1, -1):
        if locked[i] == '1':
            # If locked, check the character.
            if s[i] == ')':
                balance += 1
            else:  # s[i] == '('
                balance -= 1
        else:
            # Unlocked position: treat as ')' to help closing the open parentheses.
            balance += 1

        # If balance goes negative, then even with optimal replacements from the right, balancing fails.
        if balance < 0:
            return False

    return True

# Example Usage:
# s = "()))))", locked = "010100"
# print(canBeValid(s, locked))
← Back to All Questions