Minimize length of a given string by removing subsequences forming valid parenthesis | C ++ program of the above approach ; Function to remove all possible valid bracket subsequences ; Stores indexes of ' ( ' in valid subsequences ; Stores indexes of ' { ' in valid subsequences ; Stores indexes of ' [ ' in valid subsequences ; vis [ i ] : Check if character at i - th index is removed or not ; Mark vis [ i ] as not removed ; Iterate over the characters of string ; If current character is ' ( ' ; If current character is ' { ' ; If current character is ' [ ' ; If current character is ' ) ' and top element of A is ' ( ' ; Mark the top element of A as removed ; Mark current chacracter as removed ; If current character is ' } ' and top element of B is ' { ' ; Mark the top element of B as removed ; Mark current chacracter as removed ; If current character is ' ] ' and top element of B is ' [ ' ; Mark the top element of C as removed ; Mark current chacracter as removed ; Print the remaining characters which is not removed from S ; Driver Code ; Given string ; Size of the string ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void removeValidBracketSequences ( string & str , int N ) { stack < int > A ; stack < int > B ; stack < int > C ; bool vis [ N ] ; memset ( vis , true , sizeof ( vis ) ) ; for ( int i = 0 ; i < N ; i ++ ) { if ( str [ i ] == ' ( ' ) { A . push ( i ) ; } else if ( str [ i ] == ' { ' ) { B . push ( i ) ; } else if ( str [ i ] == ' [ ' ) { C . push ( i ) ; } else if ( str [ i ] == ' ) ' && ! A . empty ( ) ) { vis [ A . top ( ) ] = false ; A . pop ( ) ; vis [ i ] = false ; } else if ( str [ i ] == ' } ' && ! B . empty ( ) ) { vis [ B . top ( ) ] = false ; B . pop ( ) ; vis [ i ] = false ; } else if ( str [ i ] == ' ] ' && ! C . empty ( ) ) { vis [ C . top ( ) ] = false ; C . pop ( ) ; vis [ i ] = false ; } } for ( int i = 0 ; i < N ; ++ i ) { if ( vis [ i ] ) cout << str [ i ] ; } } int main ( ) { string str = " ( ( ) { ( ) ( { } ) " ; int N = str . length ( ) ; removeValidBracketSequences ( str , N ) ; return 0 ; }