Medium

Check if a Parentheses String Can Be Valid

LAB

Given s and locked, return true if unlocked positions can be changed to make s valid.

EXAMPLES

Example 1

Input
{
  "s": "))()))",
  "locked": "010100"
}

Output
true

FUNCTION SHAPE

s: stringlocked: string→bool

SOLUTION NOTE

Same greedy two-pass as Q678 wildcard validation. Unlocked positions (locked[i]='0') act as wildcards that can be either '(' or ')'.

Reveal reference solution +

pythonREFERENCE

def canBeValid(self, s: str, locked: str) -> bool:
    if len(s) % 2 == 1:
        return False

    def check(s, locked, open_char):
        balance = 0
        for i in range(len(s)):
            if s[i] == open_char or locked[i] == '0':
                balance += 1
            else:
                balance -= 1
            if balance < 0:
                return False
        return True

    return check(s, locked, '(') and check(s[::-1], locked[::-1], ')')

TimeO(n)

SpaceO(1)

Open on LeetCode ↗