Katkat
Back

Compute Minimum Parentheses Additions

ByteDanceData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

This question evaluates proficiency in string processing and algorithmic reasoning for balancing parentheses, testing understanding of invariants and edge-case handling.

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:

Input: s = "()))(("
Output: 4

Explain your approach and analyze its time and space complexity.