The approach to the problem
We should automatically think of some kind of stack solution because valid parentheses follow the last in first out order (LIFO).
- We push any "(" onto the stack, then pop off the top element from the stack whenever we find a matching ")".
- If we find a ")" when the stack is empty, that ")" must be invalid.
- After reaching the end of the string S, any remaining "("'s in the stack must be invalid as well. Because we'll be removing those "("'s by index at the end.
- The stack should include those indexes rather than just the "(".
Algorithm
- Define a stack St
-
for i in range 0 to the size of S
- if S[i] = ‘(’, then insert i into the stack St
-
otherwise, when S[i] is ‘)’, then
- if the stack is not empty, then pop from the stack, otherwise S[i] = ‘$’
-
while St is not empty,
- S[top element of stack] = ‘$’
- pop from stack
- Ans = empty string
-
for i in range 0 to the size of s
- if S[i] is not ‘$’, then Ans = Ans + S[i]
-
return Ans
Let’s understand this with an example: Input string S = “sa(nd(e(ep)”
Step by step:
We start traversing the string from the 0th index.
- i=0, S[i]= ‘s’, St = [ ] // empty
- i=1, S[i] = ‘a’, St =[ ]
- i=2, S[i] = ‘(’, St = [ 2 ] // pushed index 2
- i=3, S[i] = ‘n’, St = [ 2 ]
- i=4, S[i] = ‘d’, St = [ 2 ]
- i=5, S[i] = ‘(’, St = [ 2, 5 ] // pushed index 5
- i=6, S[i] = ‘e’, St = [ 2, 5 ]
- i=7, S[i] = ‘(’, St = [ 2, 5, 7 ] //pushed index 7
- i=8, S[i] = ‘e’, St = [ 2, 5, 7 ]
- i=9, S[i] = ‘p’, St = [ 2, 5, 7 ]
-
i=10, S[i] = ‘)’, St = [ 2, 5 ] //popped index 7
The remaining indexes in the stack are invalid, so we have to remove them to make a valid parentheses string. So, we replace those indexes with the ‘$’ symbol in the given string.
String = “sa$nd$e(ep)”
In the final step, we leave all the ‘$’ characters and copy the remaining characters in the Ans string to get the required string.
Final string = “sande(ep)”
Code in C++
#include <bits/stdc++.h>
using namespace std;
string minRemoveToMakeValid(string S) {
stack <int> St;
for (int i = 0; i < S.size(); i++) {
if (S[i] == '(')
St.push(i);
else if (S[i] == ')') {
if (!St.empty())
St.pop();
else
S[i] = '$';
}
}
while (!St.empty()) {
S[St.top()] = '$';
St.pop();
}
string Ans = "";
for (int i = 0; i < S.size(); i++) {
if (S[i] != '$')
Ans += S[i];
}
return Ans;
}
int main() {
string S;
cin >> S;
cout << minRemoveToMakeValid(S) << endl;
}
You can also try this code with Online C++ Compiler
Input 1
“j)u(h)i”
Output 1
“ju(h)i”
Input 2
“))(((“
Output 2
“”
Complexity Analysis
Time complexity- If n is the length of the string, then the time complexity is O(n) because we are running a loop of max size as the string’s length.
Space complexity- The space complexity is O(n) as the stack size can be up to the whole string’s size.
Check out this article - Balanced Parentheses
Frequently Asked Questions
What is queue data structure?
A queue is a collection of objects (a linear collection) inserted and removed using the first-in-first-out (FIFO) principle. Both ends are open in the queue data structure.
Why is stack used in C++?
The stack is a fundamental data structure for storing elements linearly. The operations on the stack are carried out in the LIFO (last in, first out) order. This means that the last element added to the stack will be the first to be removed.
How to check if a stack is empty?
stack.empty() method is used in C++ and Java. It is a boolean-type method and returns true if the stack is empty; else returns false.
Conclusion
So, this article discussed the approach to the problem- Minimum removals to make valid parentheses with the help of a stack data structure, applications of the stack, step-by-step explanation of the problem, examples, and code in C++.
Recommended Readings:
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
In case of any comments or suggestions, feel free to post them in the comments section.
250+ registered 
