Approach for the interview problem

Revision en3, by hulk_baba, 2017-09-04 18:52:35

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; } }
Tags #dp, dynamic programming

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English hulk_baba 2017-09-04 18:52:35 167
en2 English hulk_baba 2017-09-04 18:46:59 18
en1 English hulk_baba 2017-09-04 12:35:07 1422 Initial revision (published)