Given a string S consisting of characters ‘(‘, ‘)’, ‘[‘, ‘]’, ‘{‘, ‘}’, the task is to remove all balanced bracket subsequences from the string and print the remaining characters.
Examples:
Input: S = “((){()({})”
Output: “({“
Explanation:
- S[1] and S[2] forms a regular bracket sequence. Therefore, remove them from the string. S = “({()({})”
- S[2] and S[3] are regular bracket sequence. Therefore, remove them from the string. S = “({({})”
- String S[2…4] is regular bracket sequence. Therefore, remove them from the string. S = “({“
Remaining string does not contain any regular bracket sequence. Therefore, print all remaining characters.
Input: S = “{[}])(“
Output: “)(”
Approach: The idea is to use Stack data structure to solve this problem. Follow the steps below to solve the problem:
- Initialize three stacks, say A, B and C, for storing each type of parenthesis.
- Initialize a boolean array, say vis[], to mark the already visited characters.
- Store indexes of char ‘(‘ in stack A. Similarly, stacks B and C stores the positions of ‘{‘ and ‘[‘ in the string.
- Traverse through the characters of string str and perform the following:
- If the current character is ‘)‘:
- If the stack A is not empty, mark the current character in the string and vis[A.top()] as false.
- Pop the top element of the stack A.
- If the current character is ‘}’:
- If the stack B is not empty, mark the current character in the string and vis[B.top()] as false.
- Pop-out the top element of the stack B.
- If the current character is ‘]’:
- If the stack C is not empty, mark the current character in the string and vis[C.top()] as false.
- Pop-out the top element of stack C.
- If the current character is ‘)‘:
- After completing all the operations, print the characters of the string whose index is marked true in the vis[] array.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Function to remove all possible valid// bracket subsequencesvoid removeValidBracketSequences(string& str, int N){ // Stores indexes of '(' in // valid subsequences stack<int> A; // Stores indexes of '{' in // valid subsequences stack<int> B; // Stores indexes of '[' in // valid subsequences stack<int> C; // vis[i]: Check if character at // i-th index is removed or not bool vis[N]; // Mark vis[i] as not removed memset(vis, true, sizeof(vis)); // Iterate over the characters of string for (int i = 0; i < N; i++) { // If current character is '(' if (str[i] == '(') { A.push(i); } // If current character is '{' else if (str[i] == '{') { B.push(i); } // If current character is '[' else if (str[i] == '[') { C.push(i); } // If current character is ')' and // top element of A is '(' else if (str[i] == ')' && !A.empty()) { // Mark the top element // of A as removed vis[A.top()] = false; A.pop(); // Mark current character // as removed vis[i] = false; } // If current character is '}' and // top element of B is '{' else if (str[i] == '}' && !B.empty()) { // Mark the top element // of B as removed vis[B.top()] = false; B.pop(); // Mark current character // as removed vis[i] = false; } // If current character is ']' and // top element of B is '[' else if (str[i] == ']' && !C.empty()) { // Mark the top element // of C as removed vis[C.top()] = false; C.pop(); // Mark current character // as removed vis[i] = false; } } // Print the remaining characters // which is not removed from S for (int i = 0; i < N; ++i) { if (vis[i]) cout << str[i]; }}// Driver Codeint main(){ // Given string string str = "((){()({})"; // Size of the string int N = str.length(); // Function Call removeValidBracketSequences(str, N); return 0;} |
Java
// Java program of the above approachimport java.util.*; public class GFG{ // Function to remove all possible valid // bracket subsequences static void removeValidBracketSequences(String str, int N) { // Stores indexes of '(' in // valid subsequences Vector<Integer> A = new Vector<Integer>(); // Stores indexes of '{' in // valid subsequences Vector<Integer> B = new Vector<Integer>(); // Stores indexes of '[' in // valid subsequences Vector<Integer> C = new Vector<Integer>(); // vis[i]: Check if character at // i-th index is removed or not boolean[] vis = new boolean[N]; // Mark vis[i] as not removed for(int i = 0; i < N; i++) { vis[i] = true; } // Iterate over the characters of string for (int i = 0; i < N; i++) { // If current character is '(' if (str.charAt(i) == '(') { A.add(i); } // If current character is '{' else if (str.charAt(i) == '{') { B.add(i); } // If current character is '[' else if (str.charAt(i) == '[') { C.add(i); } // If current character is ')' and // top element of A is '(' else if (str.charAt(i) == ')' && (A.size() > 0)) { // Mark the top element // of A as removed vis[A.get(A.size() - 1)] = false; A.remove(A.size() - 1); // Mark current character // as removed vis[i] = false; } // If current character is '}' and // top element of B is '{' else if (str.charAt(i) == '}' && (B.size() > 0)) { // Mark the top element // of B as removed vis[B.get(B.size() - 1)] = false; B.remove(B.size() - 1); // Mark current character // as removed vis[i] = false; } // If current character is ']' and // top element of B is '[' else if (str.charAt(i) == ']' && (C.size() > 0)) { // Mark the top element // of C as removed vis[C.get(C.size() - 1)] = false; C.remove(C.size() - 1); // Mark current character // as removed vis[i] = false; } } // Print the remaining characters // which is not removed from S for (int i = 0; i < N; ++i) { if (vis[i]) System.out.print(str.charAt(i)); } } // Driver code public static void main(String[] args) { // Given string String str = "((){()({})"; // Size of the string int N = str.length(); // Function Call removeValidBracketSequences(str, N); }}// This code is contributed by divyeshrabadiya07. |
Python3
# Python3 program of the above approach# Function to remove all possible valid# bracket subsequencesdef removeValidBracketSequences(str, N): # Stores indexes of '(' in # valid subsequences A = [] # Stores indexes of '{' in # valid subsequences B = [] # Stores indexes of '[' in # valid subsequences C = [] # vis[i]: Check if character at # i-th index is removed or not vis = [True for i in range(N)] # Iterate over the characters of string for i in range(N): # If current character is '(' if (str[i] == '('): A.append(i) # If current character is '{' elif (str[i] == '{'): B.append(i) # If current character is '[' elif (str[i] == '['): C.append(i) # If current character is ')' and # top element of A is '(' elif(str[i] == ')' and len(A) != 0): # Mark the top element # of A as removed vis[A[-1]] = False A.pop() # Mark current character # as removed vis[i] = False # If current character is '}' and # top element of B is '{' elif (str[i] == '}' and len(B) != 0): # Mark the top element # of B as removed vis[B[-1]] = False B.pop() # Mark current character # as removed vis[i] = False # If current character is ']' and # top element of B is '[' elif(str[i] == ']' and len(C) != 0): # Mark the top element # of C as removed vis[C[-1]] = False C.pop() # Mark current character # as removed vis[i] = False # Print the remaining characters # which is not removed from S for i in range(N): if (vis[i]): print(str[i], end = '') # Driver Codeif __name__=='__main__': # Given string str = "((){()({})" # Size of the string N = len(str) # Function Call removeValidBracketSequences(str, N)# This code is contributed by rutvik_56 |
C#
// C# program of the above approachusing System;using System.Collections.Generic;class GFG { // Function to remove all possible valid // bracket subsequences static void removeValidBracketSequences(string str, int N) { // Stores indexes of '(' in // valid subsequences List<int> A = new List<int>(); // Stores indexes of '{' in // valid subsequences List<int> B = new List<int>(); // Stores indexes of '[' in // valid subsequences List<int> C = new List<int>(); // vis[i]: Check if character at // i-th index is removed or not bool[] vis = new bool[N]; // Mark vis[i] as not removed for(int i = 0; i < N; i++) { vis[i] = true; } // Iterate over the characters of string for (int i = 0; i < N; i++) { // If current character is '(' if (str[i] == '(') { A.Add(i); } // If current character is '{' else if (str[i] == '{') { B.Add(i); } // If current character is '[' else if (str[i] == '[') { C.Add(i); } // If current character is ')' and // top element of A is '(' else if (str[i] == ')' && (A.Count > 0)) { // Mark the top element // of A as removed vis[A[A.Count - 1]] = false; A.RemoveAt(A.Count - 1); // Mark current character // as removed vis[i] = false; } // If current character is '}' and // top element of B is '{' else if (str[i] == '}' && (B.Count > 0)) { // Mark the top element // of B as removed vis[B[B.Count - 1]] = false; B.RemoveAt(B.Count - 1); // Mark current character // as removed vis[i] = false; } // If current character is ']' and // top element of B is '[' else if (str[i] == ']' && (C.Count > 0)) { // Mark the top element // of C as removed vis[C[C.Count - 1]] = false; C.RemoveAt(C.Count - 1); // Mark current character // as removed vis[i] = false; } } // Print the remaining characters // which is not removed from S for (int i = 0; i < N; ++i) { if (vis[i]) Console.Write(str[i]); } } // Driver code static void Main() { // Given string string str = "((){()({})"; // Size of the string int N = str.Length; // Function Call removeValidBracketSequences(str, N); }}// This code is contributed by divyesh072019. |
Javascript
<script> // Javascript program of the above approach // Function to remove all possible valid // bracket subsequences function removeValidBracketSequences(str, N) { // Stores indexes of '(' in // valid subsequences let A = []; // Stores indexes of '{' in // valid subsequences let B = []; // Stores indexes of '[' in // valid subsequences let C = []; // vis[i]: Check if character at // i-th index is removed or not let vis = new Array(N); // Mark vis[i] as not removed for(let i = 0; i < N; i++) { vis[i] = true; } // Iterate over the characters of string for (let i = 0; i < N; i++) { // If current character is '(' if (str[i] == '(') { A.push(i); } // If current character is '{' else if (str[i] == '{') { B.push(i); } // If current character is '[' else if (str[i] == '[') { C.push(i); } // If current character is ')' and // top element of A is '(' else if (str[i] == ')' && (A.length > 0)) { // Mark the top element // of A as removed vis[A[A.length - 1]] = false; A.pop(); // Mark current character // as removed vis[i] = false; } // If current character is '}' and // top element of B is '{' else if (str[i] == '}' && (B.length > 0)) { // Mark the top element // of B as removed vis[B[B.length - 1]] = false; B.pop(); // Mark current character // as removed vis[i] = false; } // If current character is ']' and // top element of B is '[' else if (str[i] == ']' && (C.length > 0)) { // Mark the top element // of C as removed vis[C[C.length - 1]] = false; C.pop(); // Mark current character // as removed vis[i] = false; } } // Print the remaining characters // which is not removed from S for (let i = 0; i < N; ++i) { if (vis[i]) document.write(str[i]); } } // Given string let str = "((){()({})"; // Size of the string let N = str.length; // Function Call removeValidBracketSequences(str, N); // This code is contributed by suresh07</script> |
Output:
({
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
