Leetcode 1541: Minimum Insertions to Balance a Parentheses String
You are given a string
s containing only the characters '(' and ')'. A string is considered balanced if each '(' has a matching pair of consecutive '))' and if they appear in the correct order. Your task is to return the minimum number of insertions needed to make the string balanced.Problem
Approach
Steps
Complexity
Input: The input consists of a string `s` containing only `'('` and `')'.
Example: s = '(()))'
Constraints:
• 1 <= s.length <= 10^5
• s consists only of the characters '(' and ')'.
Output: Return the minimum number of insertions required to make the string balanced.
Example: Output: 1
Constraints:
• The string can be balanced by inserting characters anywhere in the string.
Goal: The goal is to determine how many insertions are needed to balance the string.
Steps:
• 1. Traverse through the string and use a stack to keep track of unmatched parentheses.
• 2. For every closing parenthesis, try to match it with an opening parenthesis.
• 3. If there is no match, determine how many insertions are required to balance the string.
Goal: The string length should be within the given range and consist only of `(` and `)` characters.
Steps:
• 1 <= s.length <= 10^5
• s consists of '(' and ')'.
Assumptions:
• The string is only composed of characters '(' and ')'.
• The string can be unbalanced and requires insertions to be fixed.
• Input: s = '(()))'
• Explanation: The first '(' requires one more ')' to balance the string. We add one more ')' to get '(())))'.
• Input: s = '()))'
• Explanation: No insertions are needed because the string is already balanced.
• Input: s = '))())('
• Explanation: We need to add one '(' to match the first two closing parentheses and one '))' to match the last '('.
Approach: To solve the problem, we will traverse through the string and calculate the insertions needed to balance the parentheses.
Observations:
• A stack can help match opening and closing parentheses.
• If there is an unmatched closing parenthesis, we need to add opening or closing parentheses.
• We need to traverse the string and handle unmatched parentheses by tracking them in a stack.
Steps:
• 1. Traverse through the string `s` character by character.
• 2. Use a stack to handle opening parentheses.
• 3. For each closing parenthesis, check if it has a matching opening parenthesis in the stack.
• 4. If not, calculate how many insertions are needed to balance it.
Empty Inputs:
• The string should not be empty, as the length is guaranteed to be at least 1.
Large Inputs:
• Consider strings with lengths up to 10^5 characters.
Special Values:
• Ensure the string contains only the characters '(' and ')'.
Constraints:
• The string must be within the given length and contain only valid characters.
int minInsertions(string s) {
int res = 0;
int n = s.size();
stack<char> stk;
for(int i = 0; i < n; i++) {
if(s[i] == '(') {
stk.push('(');
continue;
}
if(i + 1 < n && s[i + 1] == ')') {
if(!stk.empty()) stk.pop();
else res++;
i++;
} else {
if(!stk.empty()) {stk.pop(); res++;}
else res += 2;
}
}
return res + stk.size() * 2;
}
1 : Variable Initialization
int minInsertions(string s) {
This line declares the function `minInsertions` which takes a string `s` as input and returns an integer value representing the minimum insertions required.
2 : Variable Initialization
int res = 0;
The variable `res` is initialized to 0. This will keep track of the number of insertions needed.
3 : String Length Calculation
int n = s.size();
Here, the variable `n` is set to the size of the string `s`, which is the total number of characters in the string.
4 : Stack Initialization
stack<char> stk;
A stack `stk` is created to help keep track of unmatched opening parentheses as we process the string.
5 : Loop
for(int i = 0; i < n; i++) {
A loop begins to iterate through each character of the string `s`.
6 : Conditional Statement
if(s[i] == '(') {
If the current character is an opening parenthesis, we proceed to push it onto the stack.
7 : Stack Operations
stk.push('(');
Push the opening parenthesis onto the stack.
8 : Control Flow
continue;
Skip the rest of the loop and move to the next character if it's an opening parenthesis.
9 : Conditional Statement
if(i + 1 < n && s[i + 1] == ')') {
Check if the current character is followed by a closing parenthesis.
10 : Stack Operations
if(!stk.empty()) stk.pop();
If the stack is not empty, pop the top item (the matching opening parenthesis).
11 : Result Calculation
else res++;
If the stack is empty (no unmatched opening parenthesis), increment `res` by 1 as we need to insert a new opening parenthesis.
12 : Increment
i++;
Skip the next character (closing parenthesis) since it was already processed.
13 : Else Block
} else {
If the current character is not followed by a closing parenthesis, handle the unmatched parenthesis.
14 : Stack Operations
if(!stk.empty()) {stk.pop(); res++;}
If there's an unmatched opening parenthesis in the stack, pop it and increment the `res` counter by 1.
15 : Result Calculation
else res += 2;
If the stack is empty, two insertions are needed—one opening parenthesis and one closing parenthesis.
16 : Return Statement
return res + stk.size() * 2;
Return the result, adding any remaining unmatched opening parentheses in the stack, each requiring two insertions.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: We need to traverse the string once, which gives a time complexity of O(n).
Best Case: O(n)
Worst Case: O(n)
Description: We use a stack to store the unmatched parentheses, so the space complexity is O(n).
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus