Number of ways of choosing K equal substrings of any length for every query | Java 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
import java . util . HashMap ; class GFG { static int maxlen = 100 ; public static void generateSubStrings ( String s , HashMap < String , Integer > mpp ) { int l = s . length ( ) ; for ( int i = 0 ; i < l ; i ++ ) { String temp = " " ; for ( int j = i ; j < l ; j ++ ) { temp += s . charAt ( j ) ; if ( mpp . containsKey ( temp ) ) { int x = mpp . get ( temp ) ; mpp . put ( temp , ++ x ) ; } else mpp . put ( temp , 1 ) ; } } } public static void binomialCoeff ( int [ ] [ ] C ) { int 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 ] ; } } } public static int answerQuery ( HashMap < String , Integer > mpp , int [ ] [ ] C , int k ) { int ans = 0 ; for ( HashMap . Entry < String , Integer > entry : mpp . entrySet ( ) ) { if ( entry . getValue ( ) >= k ) ans += C [ entry . getValue ( ) ] [ k ] ; } return ans ; } public static void main ( String [ ] args ) { String s = " aabaab " ; HashMap < String , Integer > mpp = new HashMap < > ( ) ; generateSubStrings ( s , mpp ) ; int [ ] [ ] C = new int [ maxlen ] [ maxlen ] ; binomialCoeff ( C ) ; int [ ] queries = { 2 , 3 , 4 } ; int q = queries . length ; for ( int i = 0 ; i < q ; i ++ ) System . out . println ( answerQuery ( mpp , C , queries [ i ] ) ) ; } }