LeetCode 1541: Minimum Insertions to Balance a Parentheses String Solution

Master LeetCode problem 1541 (Minimum Insertions to Balance a Parentheses String), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1541. Minimum Insertions to Balance a Parentheses String

Medium

String Stack Greedy

Problem Explanation

Explanation:

To solve this problem, we can use a stack to keep track of the open parentheses '('. We iterate through the input string and for each character:

If it is '(', we push it onto the stack.
If it is ')', we check the top of the stack. If it is ')', we know we have a balanced pair so we pop the stack. If it is '(', we need to add a closing ')' to balance the string.

At the end, any remaining '(' in the stack need a corresponding ')' to balance the string. The total number of insertions needed is equal to the number of remaining '(' in the stack plus the number of ')' needed to balance any unpaired '('.

Time Complexity:

The time complexity of this solution is O(n), where n is the length of the input string.

Space Complexity:

The space complexity of this solution is O(n) to store the stack.

Solution Code

class Solution {
    public int minInsertions(String s) {
        Stack<Character> stack = new Stack<>();
        int inserts = 0;
        
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    inserts++;
                } else {
                    stack.pop();
                    if (!stack.isEmpty() && stack.peek() == '(') {
                        stack.pop();
                    } else {
                        inserts++;
                    }
                }
            }
        }
        
        inserts += stack.size() * 2;
        
        return inserts;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1541 (Minimum Insertions to Balance a Parentheses String)?

This page provides optimized solutions for LeetCode problem 1541 (Minimum Insertions to Balance a Parentheses String) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1541 (Minimum Insertions to Balance a Parentheses String)?

The time complexity for LeetCode 1541 (Minimum Insertions to Balance a Parentheses String) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1541 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1541 in Java, C++, or Python.

Back to LeetCode Solutions