Problem:
Given a string consisting of opening and closing parenthesis, find length of the longest valid parenthesis sub string.[Courtesy: geeksforgeeks]
Solution: The problem can be solved with DP approach . And also as counting the left and right parenthesis from left to right.If the left parenthesis count is less than the right parenthesis count , then it means that validity of the parsed string is invalid from this point. Find the longest valid length when left and right counts are equal . Start counting again left and right parenthesis count from 0 when left becomes less than right count.
Do the above approach from right to left of the string again.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
#include <stdio.h> #include <stack> #include <string> #include <iostream> using namespace std; int main() { //code int t; scanf("%d",&t); while(t--) { string s; cin>>s; int len=0; int max_len=0; int max_push_count=0; bool disConnected; int left=0,right=0; for(int i=0;i<s.size();i++) { if(s[i]=='(') { left+=1; } if(s[i]==')') { right+=1; } if(left==right) { max_len = (max_len<(left*2)?(left*2):max_len); } if(left<right) { left=0; right=0; } } left=0;right=0; for(int i=s.size()-1;i>=0;i--) { if(s[i]==')') { left+=1; } if(s[i]=='(') { right+=1; } if(left==right) { max_len = (max_len<(left*2)?(left*2):max_len); } if(left<right) { left=0; right=0; } } cout<<max_len<<endl; } return 0; } |
DP approach:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
#include <stdio.h> #include <queue> #include <string> #include <queue> #include <iostream> using namespace std; /* Input: 2 ((() )()()) Output: 2 4 )(() ans=2 ()(((()()) ans=6 */ int dp[10005]; int main() { //code int t; string s; int MX; cin>>t; while(t--) { cin>>s; for(int i=0;i<10005;i++) dp[i]=0; if(s[1]==')' && s[0]=='(') dp[1]=2; if(s[1]==')' && s[0]==')') dp[1]=0; if(s[1]=='(') dp[1]=0; MX=dp[1]; for(int i=2;i<s.size();i++) { if(s[i]==')' && s[i-1]=='(') dp[i]=dp[i-2]+2; if(s[i]==')' && s[i-1]==')') { if(s[i-dp[i-1]-1]=='(') dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]; } if(dp[i]>MX) MX=dp[i]; } cout<<MX<<endl; } return 0; } |