Compute Minimum Parentheses Additions
Company: Bytedance
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a string `s` consisting only of the characters `'('` and `')'`, compute the minimum number of parentheses that must be inserted anywhere in the string so that the resulting string is a valid parentheses string.
A valid parentheses string is one where every opening parenthesis has a matching closing parenthesis, every closing parenthesis matches a previous unmatched opening parenthesis, and the pairs are properly nested.
Return a single integer: the minimum number of insertions required.
Example:
```text
Input: s = "()))(("
Output: 4
```
Explain your approach and analyze its time and space complexity.
Quick Answer: This question evaluates proficiency in string processing and algorithmic reasoning for balancing parentheses, testing understanding of invariants and edge-case handling.
Return the minimum number of parentheses insertions needed to make s valid.
Constraints
- s contains only '(' and ')'
Examples
Input: ('()))((',)
Expected Output: 4
Explanation: Given example.
Input: ('',)
Expected Output: 0
Explanation: Empty string is already valid.
Input: ('(((',)
Expected Output: 3
Explanation: Needs closing parentheses.
Input: (')))',)
Expected Output: 3
Explanation: Needs opening parentheses.
Input: ('()()',)
Expected Output: 0
Explanation: Already valid.
Hints
- Count unmatched closing parentheses and unmatched openings.