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;
    }
}