Number of ways of choosing K equal substrings of any length for every query | JavaScript implementation of the approach ; Function to generate all the sub - strings ; Length of the string ; Generate all sub - strings ; Count the occurrence of every sub - string ; Compute the Binomial Coefficient ; Calculate value of Binomial Coefficient in bottom up manner ; Base Cases ; Calculate value using previously stored values ; Function to return the result for a query ; Iterate for every unique sub - string ; Count the combinations ; Driver code ; Get all the sub - strings Store the occurrence of all the sub - strings ; Pre - computation ; Queries ; Perform queries
let maxlen = 100 ; function generateSubStrings ( s , mpp ) { let l = s . length ; for ( let i = 0 ; i < l ; i ++ ) { let temp = " " ; for ( let j = i ; j < l ; j ++ ) { temp += s [ j ] ; if ( mpp . has ( temp ) ) { let x = mpp . get ( temp ) ; mpp . set ( temp , ++ x ) ; } else mpp . set ( temp , 1 ) ; } } } function binomialCoeff ( C ) { let i , j ; for ( i = 1 ; i < 100 ; i ++ ) { for ( j = 0 ; j < 100 ; j ++ ) { if ( j == 0 j == i ) C [ i ] [ j ] = 1 ; else C [ i ] [ j ] = C [ i - 1 ] [ j - 1 ] + C [ i - 1 ] [ j ] ; } } } function answerQuery ( mpp , C , k ) { let ans = 0 ; for ( let [ key , value ] of mpp . entries ( ) ) { if ( value >= k ) ans += C [ value ] [ k ] ; } return ans ; } let s = " " ; let mpp = new Map ( ) ; generateSubStrings ( s , mpp ) ; let C = new Array ( maxlen ) ; for ( let i = 0 ; i < maxlen ; i ++ ) { C [ i ] = new Array ( maxlen ) ; for ( let j = 0 ; j < maxlen ; j ++ ) C [ i ] [ j ] = 0 ; } binomialCoeff ( C ) ; let queries = [ 2 , 3 , 4 ] ; let q = queries . length ; for ( let i = 0 ; i < q ; i ++ ) document . write ( answerQuery ( mpp , C , queries [ i ] ) + " " ) ;