NeetCode #796LC-2116MediumGreedy
← Back to All Problems#796 · #2116 · Check if a Parentheses String Can Be Valid(判断一个括号字符串是否有效)
📌 Problem Statement & Constraints
You are given a string
s of ( and ), and a binary string locked where 1 means the character is locked (unchangeable) and 0 means it may be flipped. Return true if s can be turned into a valid parentheses string. Constraints: 1 <= s.length <= 10^5, locked.length == s.length, s[i] is ( or ), locked[i] is 0 or 1.💡 Core Algorithmic Approaches
- A valid string must have even length, so an odd length is an immediate false.
- Scan left to right treating every unlocked position as
(: if the balance ever goes negative, there are too many locked)and it is invalid. - Scan right to left treating every unlocked position as
): if the balance ever goes negative, there are too many locked(. - Passing both scans is necessary and sufficient, because the unlocked characters can be assigned to satisfy whichever direction needs them.
💻 Benchmark Python3 Implementation
class Solution:
def canBeValid(self, s: str, locked: str) -> bool:
n = len(s)
if n % 2:
return False
bal = 0
for i in range(n): # unlocked behaves as '('
if locked[i] == "0" or s[i] == "(":
bal += 1
else:
bal -= 1
if bal < 0:
return False
bal = 0
for i in range(n - 1, -1, -1): # unlocked behaves as ')'
if locked[i] == "0" or s[i] == ")":
bal += 1
else:
bal -= 1
if bal < 0:
return False
return True⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): two linear passes.
💾 Space Complexity
O(1): one balance counter.
⚠️ Interview Pitfalls & Follow-ups
- Using a single pass: one direction cannot detect both failure modes, so two passes are required.
- Forgetting the odd-length check: a string of odd length can never be valid.
- Treating unlocked positions as fixed: they are the wildcards that make the string flexible.
- Mismatching the wildcard direction: left to right the wildcard acts as
(, right to left as).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.