Count distinct substrings that contain some characters at most k times | Python3 implementation of the approach ; Function to return the count of valid sub - strings ; Store all characters of anotherStr in a direct index table for quick lookup . ; To store distinct output substrings ; Traverse through the given string and one by one generate substrings beginning from s [ i ] . ; One by one generate substrings ending with s [ j ] ; If character is illegal ; If current substring is valid ; If current substring is invalid , adding more characters would not help . ; Return the count of distinct sub - strings ; Driver code
MAX_CHAR = 256 NEW_LINE def countSubStrings ( s , anotherStr , k ) : NEW_LINE INDENT illegal = [ False ] * MAX_CHAR NEW_LINE for i in range ( len ( anotherStr ) ) : NEW_LINE INDENT illegal [ ord ( anotherStr [ i ] ) ] = True NEW_LINE DEDENT us = set ( ) NEW_LINE for i in range ( len ( s ) ) : NEW_LINE INDENT ss = " " NEW_LINE count = 0 NEW_LINE for j in range ( i , len ( s ) ) : NEW_LINE INDENT if ( illegal [ ord ( s [ j ] ) ] ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT ss = ss + s [ j ] NEW_LINE if ( count <= k ) : NEW_LINE INDENT us . add ( ss ) NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT DEDENT return len ( us ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT string = " acbacbacaa " NEW_LINE anotherStr = " abcdefghijklmnopqrstuvwxyz " NEW_LINE k = 2 NEW_LINE print ( countSubStrings ( string , anotherStr , k ) ) NEW_LINE DEDENT