Minimum Add to Make Parentheses Valid 🎯

Welcome to a fascinating journey into the world of Data Structures and Algorithms! Today, we're going to learn about a problem that involves parentheses and finding the minimum additions required to make them valid. Let's dive right in!

Understanding the Problem 📝

In this problem, we are given a string containing (' and ') but not necessarily balanced. The task is to find the minimum number of parentheses we need to add to make the entire string balanced.

Example:

Consider the string (())((())). Here, we have more opening brackets than closing ones. To make it balanced, we need to add 3 closing brackets: (())((())) → (())((()))))

Breaking it Down 💡

Let's break down the problem:

We start iterating through the string from left to right.
If we encounter an opening bracket ( at any position, we increase a counter open.
If we encounter a closing bracket ) at any position, we increase a counter close.
At the end of the iteration, if open > close, we know that we need to add open - close pairs of parentheses.

Now, let's see how to solve this problem using a simple Python solution.

Solving the Problem with Python 💡

python

def minAddToMakeValid(s: str) -> int:
    open_brackets = 0
    close_brackets = 0

    for bracket in s:
        if bracket == '(':
            open_brackets += 1
        elif bracket == ')':
            if open_brackets > 0:
                open_brackets -= 1
            else:
                close_brackets += 1

    return open_brackets + close_brackets

Explanation:

We initialize open_brackets and close_brackets to 0.
We iterate through each bracket in the string s.
If we encounter an opening bracket, we increase open_brackets.
If we encounter a closing bracket, we check if there are any open brackets left. If yes, we decrement open_brackets. If not, we increment close_brackets.
Finally, we return the sum of both counters, which represents the minimum number of parentheses needed to make the string balanced.

Practice Time 💡

Now that you've understood the concept, it's time to practice! Let's solve a few problems on our own.

That's it for today! We've learned about the problem of finding the minimum number of parentheses to make a string balanced. I hope you enjoyed this lesson, and don't forget to practice to reinforce your understanding.

In the next lesson, we'll delve deeper into more complex problems and data structures. Stay tuned! 🎯