⚡Flashcard Drill➔
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

  1. A valid string must have even length, so an odd length is an immediate false.
  2. Scan left to right treating every unlocked position as (: if the balance ever goes negative, there are too many locked ) and it is invalid.
  3. Scan right to left treating every unlocked position as ): if the balance ever goes negative, there are too many locked (.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems