Count distinct substrings that contain some characters at most k times | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX_CHAR = 256 ; int countSubStrings ( string s , string anotherStr , int k ) { bool illegal [ MAX_CHAR ] = { false } ; for ( int i = 0 ; i < anotherStr . size ( ) ; i ++ ) illegal [ anotherStr [ i ] ] = true ; unordered_set < string > us ; for ( int i = 0 ; i < s . size ( ) ; ++ i ) { string ss = " " ; int count = 0 ; for ( int j = i ; j < s . size ( ) ; ++ j ) { if ( illegal [ s [ j ] ] ) ++ count ; ss = ss + s [ j ] ; if ( count <= k ) { us . insert ( ss ) ; } else break ; } } return us . size ( ) ; } int main ( ) { string str = " acbacbacaa " ; string anotherStr = " abcdefghijklmnopqrstuvwxyz " ; int k = 2 ; cout << countSubStrings ( str , anotherStr , k ) ; return 0 ; }