Compute unmatched parentheses length

Q: Compute unmatched parentheses length

This is a Coding & Algorithms interview question from Meta for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

Problem

You are given a string s consisting only of characters '(' and ')'.

Repeatedly remove any matched pair of parentheses as part of a valid parentheses matching (equivalently, cancel out all valid matches). After all possible matches are removed, return the number of remaining characters (the count of unmatched parentheses).

Examples

s = "()" → all matched → return 0
s = "())" → one pair matched, one ')' unmatched → return 1
s = "(()" → one pair matched, one '(' unmatched → return 1
s = ")()(" → two matched in the middle, ends unmatched → return 2

Function signature

Input: s: string
Output: int

Constraints

0 <= len(s) <= 10^6 (design for linear time)

Notes

You only need to return the number of unmatched parentheses, not the corrected string.