Find a valid parenthesis sequence of length K from a given valid parenthesis sequence | C ++ program for the above approach ; Function to find the subsequence of length K forming valid sequence ; Stores the resultant string ; Check whether character at index i is visited or not ; Traverse the string ; Push index of open bracket ; Pop and mark visited ; Increment count by 2 ; Append the characters and create the resultant string ; Return the resultant string ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE #define ll  long long NEW_LINE using namespace std ; string findString ( string s , int k ) { int n = s . length ( ) ; string ans = " " ; stack < int > st ; vector < bool > vis ( n , false ) ; int count = 0 ; Vector < boolean > vis ( n , false ) ; for ( int i = 0 ; i < n ; ++ i ) { if ( s [ i ] == ' ( ' ) { st . push ( i ) ; } if ( count < k && s [ i ] == ' ) ' ) { vis [ st . top ( ) ] = 1 ; st . pop ( ) ; vis [ i ] = true ; count += 2 ; } } for ( int i = 0 ; i < n ; ++ i ) { if ( vis [ i ] == true ) { ans += s [ i ] ; } } return ans ; } int main ( ) { string s = " ( ) ( ) ( ) " ; int K = 2 ; cout << findString ( s , K ) ; }