Number of ways of choosing K equal substrings of any length for every query | Python3 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
from collections import defaultdict NEW_LINE maxlen = 100 NEW_LINE def generateSubStrings ( s , mpp ) : NEW_LINE INDENT l = len ( s ) NEW_LINE for i in range ( 0 , l ) : NEW_LINE INDENT temp = " " NEW_LINE for j in range ( i , l ) : NEW_LINE INDENT temp += s [ j ] NEW_LINE mpp [ temp ] += 1 NEW_LINE DEDENT DEDENT DEDENT def binomialCoeff ( C ) : NEW_LINE INDENT for i in range ( 0 , 100 ) : NEW_LINE INDENT for j in range ( 0 , 100 ) : NEW_LINE INDENT if j == 0 or j == i : NEW_LINE INDENT C [ i ] [ j ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT C [ i ] [ j ] = C [ i - 1 ] [ j - 1 ] + C [ i - 1 ] [ j ] NEW_LINE DEDENT DEDENT DEDENT DEDENT def answerQuery ( mpp , C , k ) : NEW_LINE INDENT ans = 0 NEW_LINE for it in mpp : NEW_LINE INDENT if mpp [ it ] >= k : NEW_LINE INDENT ans += C [ mpp [ it ] ] [ k ] NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " aabaab " NEW_LINE mpp = defaultdict ( lambda : 0 ) NEW_LINE generateSubStrings ( s , mpp ) NEW_LINE C = [ [ 0 for i in range ( maxlen ) ] for j in range ( maxlen ) ] NEW_LINE binomialCoeff ( C ) NEW_LINE queries = [ 2 , 3 , 4 ] NEW_LINE q = len ( queries ) NEW_LINE for i in range ( 0 , q ) : NEW_LINE INDENT print ( answerQuery ( mpp , C , queries [ i ] ) ) NEW_LINE DEDENT DEDENT