Hello I was asked this problem in an interview
Given a string(S) consisting of only open & closed brackets, you need to tell the no. of ways to assign each bracket as ‘X’ or ‘Y’ such that when you traverse the string from left to right, the 2 strings formed by each ‘X’ and ‘Y’ are both balanced.
Example:
Input String : (())
1) XYXY
XX : ()
YY : ()
2) XXXX
3) YYYY
Output - 6
Explantion-{XXXX,YYYY,XYYX,YXXY,XYXY,YXYX}
I was able to come up with O(N^3) solution but the interviewer wanted an O(N^2) solution. I considered three states in my DP, current index, number of X seen, number of Y seen. Please see my code. If somebody can please share better solutions O(N^2) or even better than O(N^2). Thank you.
string s ;
int Count[N][N][N] ;
int NumberOfStrings(int curr , int Xc, int Yc ){
if(curr==s.size())
return 1 ;
int count = 0 ;
int s1,s2;
if(s[curr] == '('){
s1 = NumberOfStrings(curr+1 , Xc+1 , Yc) ;
s2 = NumberOfStrings(curr+1 , Xc , Yc+1) ;
Count[Xc][Yc][curr] = s2+s1;
return s1+s2;
}
if(dp[Xc][Yc][curr])
return dp[Xc][Yc][curr] ;
else{
if(Xc >= 1 ){
s1 = NumberOfStrings(curr+1, Xc-1 , Yc) ;
}
if(Yc >= 1){
s2 = NumberOfStrings(curr+1, Xc, Yc-1 ) ;
}
Count[Xc][Yc][curr] = s1+s2;
return s1+s2;
}
}