Katkat
Back

Compute unmatched parentheses length

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to use stack-based logic to track balanced sequences and identify the length of characters that remain unmatched after processing all valid pairs.

Problem Statement

Given a string s consisting of only parentheses '(' and ')', calculate the total number of characters that are not part of any valid matching pair. A matching pair consists of a '(' followed by a ')'.

Your task is to implement a function count_unmatched(s) that returns an integer representing the count of unmatched parentheses.

Constraints

  • 0 <= len(s) <= 10^5
  • The string contains only '(' and ')' characters.

Examples

Example 1: Input: s = "()()" Output: 0 Explanation: Every parenthesis is matched.

Example 2: Input: s = "((()" Output: 2 Explanation: The first two '(' characters do not have corresponding closing parentheses.

Example 3: Input: s = ")()(" Output: 2 Explanation: The first ')' and the last '(' cannot be matched.

Edge Cases

  • Empty string.
  • String with no matches (e.g., "))))" or "((((").
  • String with complex nesting (e.g., "(()(())").

Hints

Hint 1

Consider using a counter to keep track of currently open parentheses that are waiting for a match.

Hint 2

If you encounter a ')' when the counter is zero, that character is definitely unmatched, and you should increment a separate tracker for 'bad' closers.

Hint 3

At the end of the iteration, the total unmatched count is the sum of any remaining unclosed '(' and the count of 'bad' closing parentheses.

Follow-up questions

  • How would your logic change if the input included other types of brackets like '[' and '{'?
  • Can you return the indices of the unmatched parentheses instead of just their count?
  • What is the space complexity of your solution, and can it be improved if we are only interested in the count?