Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Solution: Minimum Add to Make Parentheses Valid

Problem Statement

Given a string str containing '(' and ')' characters, find the minimum number of parentheses that need to be added to a string of parentheses to make it valid.

A valid string of parentheses is one where each opening parenthesis '(' has a corresponding closing parenthesis ')' and vice versa. The goal is to determine the least amount of additions needed to achieve this balance.

Examples

  1. Example 1:
    • Input: "(()"
    • Expected Output: 1
    • Justification: The string has two opening parentheses and one closing parenthesis

.....

.....

.....

Like the course? Get enrolled and start learning!
SHLOK KOTHARI

SHLOK KOTHARI

· 2 years ago

I am not completely sure how this problem employs a greedy strategy, but here is my understanding. As soon as the number of closed brackets exceeds the number of open brackets, we plan to handle it. Even if there is only one mismatch, we increase the counter and reduce the balance. This approach works for this problem because traversing from the beginning ensures we have all the information about the preceding brackets, which is sufficient to obtain the solution at the current position.

Let me know if I am thinking wrong here. Thanks!

Show 1 reply