Given a string S consisting of ‘(‘, ‘)’, ‘[‘ and ‘]’, the task is to find the minimum count of remaining characters in the string by removing subsequences of the valid parenthesis.
Examples:
Input: S = “[]])([”
Output: 4
Explanation:
Removing the subsequence { str[0], str[1] } modifies S to “])([“.
Therefore, the required output is 4.Input: S = “([)(])”
Output: 0
Explanation:
Removing the subsequence { str[0], str[2] } modifies S to “[(])”.
Removing the subsequence { str[0], str[2] } modifies S to “()”.
Removing the subsequence { str[0], str[1] } modifies S to “”.
Therefore, the required output is 0.
Approach: The problem can be solved using Stack. Follow the steps below to solve the problem:
- The idea is to handle the round parenthesis, ‘()’ and the bracket parenthesis, ‘[]’ in two separate stacks.
- Initialize two variables say, roundCount and squareCount to store the count of opening parenthesis in valid parenthesis of ‘()’ and ‘[]’ respectively.
- Iterate over each character of the given string and calculate the length of valid parenthesis of ‘()’ and ‘[]’ using two different stacks.
- Finally, print the value of (N – 2 * (roundCount + squareCount)).
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum count of remaining// characters left into the string by removing// the valid subsequencesvoid deleteSubseq(string s){ // Length of the string int N = s.size(); // Stores opening parenthesis // '(' of the given string stack<char> roundStk; // Stores square parenthesis // '[' of the given string stack<char> squareStk; // Stores count of opening parenthesis '(' // in valid subsequences int roundCount = 0; // Stores count of opening parenthesis '[' // in valid subsequences int squareCount = 0; // Iterate over each // characters of S for (int i = 0; i < N; i++) { // If current character is '[' if (s[i] == '[') { // insert into stack squareStk.push(s[i]); } // If i is equal to ']' else if (s[i] == ']') { // If stack is not empty and // top element of stack is '[' if (squareStk.size() != 0 && squareStk.top() == '[') { // Remove top element from stack squareStk.pop(); // Update squareCount squareCount += 1; } } // If current character is '(' else if (s[i] == '(') { // Insert into stack roundStk.push(s[i]); } // If i is equal to ')' else { // If stack is not empty and // top element of stack is '(' if (roundStk.size() != 0 && squareStk.top() == '(') { // Remove top element from stack squareStk.pop(); // Update roundCount roundCount += 1; } } } // Print the minimum number of remaining // characters left into S cout << (N - (2 * squareCount + 2 * roundCount));}// Driver codeint main(){ // input string string s = "[]])(["; // function call deleteSubseq(s);}// This code is contributed by gauravrajput1 |
Java
/*package whatever //do not write package name here */// Java program for the above approachimport java.io.*;import java.util.Stack;class GFG { // Function to find the minimum count of remaining // characters left into the string by removing // the valid subsequences public static void deleteSubseq(String s) { // Length of the string int N = s.length(); // Stores opening parenthesis // '(' of the given string Stack<Character> roundStk = new Stack<>(); // Stores square parenthesis // '[' of the given string Stack<Character> squareStk = new Stack<>(); // Stores count of opening parenthesis '(' // in valid subsequences int roundCount = 0; // Stores count of opening parenthesis '[' // in valid subsequences int squareCount = 0; // Iterate over each // characters of S for (int i = 0; i < N; i++) { // If current character is '[' if (s.charAt(i) == '[') { // insert into stack squareStk.push(s.charAt(i)); } // If i is equal to ']' else if (s.charAt(i) == ']') { // If stack is not empty and // top element of stack is '[' if (squareStk.size() != 0 && squareStk.peek() == '[') { // Remove top element from stack squareStk.pop(); // Update squareCount squareCount += 1; } } // If current character is '(' else if (s.charAt(i) == '(') { // Insert into stack roundStk.push(s.charAt(i)); } // If i is equal to ')' else { // If stack is not empty and // top element of stack is '(' if (roundStk.size() != 0 && squareStk.peek() == '(') { // Remove top element from stack squareStk.pop(); // Update roundCount roundCount += 1; } } } // Print the minimum number of remaining // characters left into S System.out.println( N - (2 * squareCount + 2 * roundCount)); } // Driver code public static void main(String[] args) { // input string String s = "[]])(["; // function call deleteSubseq(s); }}// This code is contributed by aditya7409 |
Python3
# Python program for the above approach# Function to find the minimum count of remaining# characters left into the string by removing # the valid subsequences def deleteSubseq(S): # Length of the string N = len(S) # Stores opening parenthesis # '(' of the given string roundStk = [] # Stores square parenthesis # '[' of the given string squareStk = [] # Stores count of opening parenthesis '(' # in valid subsequences roundCount = 0 # Stores count of opening parenthesis '[' # in valid subsequences squareCount = 0 # Iterate over each # characters of S for i in S: # If current character is '[' if i == '[': # Insert into stack squareStk.append(i) # If i is equal to ']' elif i == ']': # If stack is not empty and # top element of stack is '[' if squareStk and squareStk[-1] == '[': # Remove top element from stack squareStk.pop() # Update squareCount squareCount += 1 # If current character is '(' elif i == '(': # Insert into stack roundStk.append(i) else: # If stack is not empty and # top element of stack is '(' if roundStk and roundStk[-1] == '(': # Remove top element from stack roundStk.pop() # Update roundCount roundCount += 1 # Print the minimum number of remaining # characters left into S print(N - (2 * squareCount + 2 * roundCount))# Driver Codeif __name__ == '__main__': # Given string S = '[]])([' # Function Call deleteSubseq(S) |
C#
/*package whatever //do not write package name here */// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to find the minimum count of remaining // characters left into the string by removing // the valid subsequences public static void deleteSubseq(String s) { // Length of the string int N = s.Length; // Stores opening parenthesis // '(' of the given string Stack<char> roundStk = new Stack<char>(); // Stores square parenthesis // '[' of the given string Stack<char> squareStk = new Stack<char>(); // Stores count of opening parenthesis '(' // in valid subsequences int roundCount = 0; // Stores count of opening parenthesis '[' // in valid subsequences int squareCount = 0; // Iterate over each // characters of S for (int i = 0; i < N; i++) { // If current character is '[' if (s[i] == '[') { // insert into stack squareStk.Push(s[i]); } // If i is equal to ']' else if (s[i] == ']') { // If stack is not empty and // top element of stack is '[' if (squareStk.Count != 0 && squareStk.Peek() == '[') { // Remove top element from stack squareStk.Pop(); // Update squareCount squareCount += 1; } } // If current character is '(' else if (s[i] == '(') { // Insert into stack roundStk.Push(s[i]); } // If i is equal to ')' else { // If stack is not empty and // top element of stack is '(' if (roundStk.Count != 0 && squareStk.Peek() == '(') { // Remove top element from stack squareStk.Pop(); // Update roundCount roundCount += 1; } } } // Print the minimum number of remaining // characters left into S Console.WriteLine( N - (2 * squareCount + 2 * roundCount)); } // Driver code public static void Main(String[] args) { // input string String s = "[]])(["; // function call deleteSubseq(s); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program for the above approach// Function to find the minimum count of remaining// characters left into the string by removing// the valid subsequencesfunction deleteSubseq(s){ // Length of the string var N = s.length; // Stores opening parenthesis // '(' of the given string var roundStk = []; // Stores square parenthesis // '[' of the given string var squareStk = []; // Stores count of opening parenthesis '(' // in valid subsequences var roundCount = 0; // Stores count of opening parenthesis '[' // in valid subsequences var squareCount = 0; // Iterate over each // characters of S for (var i = 0; i < N; i++) { // If current character is '[' if (s[i] == '[') { // insert into stack squareStk.push(s[i]); } // If i is equal to ']' else if (s[i] == ']') { // If stack is not empty and // top element of stack is '[' if (squareStk.length != 0 && squareStk[squareStk.length-1] == '[') { // Remove top element from stack squareStk.pop(); // Update squareCount squareCount += 1; } } // If current character is '(' else if (s[i] == '(') { // Insert into stack roundStk.push(s[i]); } // If i is equal to ')' else { // If stack is not empty and // top element of stack is '(' if (roundStk.length != 0 && squareStk[squareStk.length-1] == '(') { // Remove top element from stack squareStk.pop(); // Update roundCount roundCount += 1; } } } // Print the minimum number of remaining // characters left into S document.write(N - (2 * squareCount + 2 * roundCount));}// Driver code// input stringvar s = "[]])([";// function calldeleteSubseq(s);</script> |
Output:
4
Time Complexity: O(N) where n is number of elements in given string. As, we are using a loop to traverse N times so it will cost us O(N) time.
Auxiliary Space: O(N), as we are using extra space for stack.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
