Minimum Insertions To Balance A Parentheses String - Leetcode Solution

Problem Statement: Given a string s containing only parentheses '(', ')' find the minimum number of insertions required to balance the parentheses string.

Example 1: Input: s = "(()))" Output: 1 Explanation: The input string is unbalanced, we can add ')' at the end, resulting in "(())))" to balance the string.

Example 2: Input: s = "())" Output: 0 Explanation: The input string is already balanced.

Solution Approach: We can use a stack to solve this problem. The idea is to traverse the given string s character by character. If we encounter an opening parenthesis '(', we push it onto the stack. If we encounter a closing parenthesis ')', we check if the stack is non-empty and the top of the stack contains an opening parenthesis '('. If both conditions are true, we can pop from the stack and move on. Otherwise, we insert an opening parenthesis '(' to balance the string.

At the end of traversing the input string s, if the stack is non-empty, it means there are unmatched opening parenthesis '('. Hence, we need to insert an equal number of closing parenthesis ')'s to balance the string.

Time Complexity: O(N) Space Complexity: O(N)

Implementation:

class Solution { public: int minInsertions(string s) { stack<char> st; int ans = 0; int i = 0; while (i < s.length()) { if (s[i] == '(') { st.push(s[i]); i++; } else { if (i+1 < s.length() && s[i+1] == ')') { // Case 1: consecutive closing parenthesis ')' if (st.empty()) { ans++; // Missing opening parenthesis '(' } i += 2; } else { // Case 2: single closing parenthesis ')' if (st.empty()) { ans += 2; // Missing opening & closing parenthesis '(' & ')' } else { st.pop(); } i++; } } } while (!st.empty()) { // Unmatched opening parenthesis '(' ans += 2; // Need to insert a closing parenthesis ')' st.pop(); } return ans; } };

Example Run: Input: "(()))" Output: 1 Explanation: i=0: '(' pushed onto the stack, st=(, i=1 i=1: '(' pushed onto the stack, st=(, (, i=2 i=2: ')' matches last opening parenthesis, st=(, i=3 i=3: ')' matches last opening parenthesis, st=(), i=4

Answer is 1.

1