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
using System ; using System . Collections . Generic ; class GFG { static int MAX_CHAR = 256 ; static int countSubStrings ( String s , String anotherStr , int k ) { bool [ ] illegal = new bool [ MAX_CHAR ] ; for ( int i = 0 ; i < anotherStr . Length ; i ++ ) { illegal [ anotherStr [ i ] ] = true ; } HashSet < String > us = new HashSet < String > ( ) ; for ( int i = 0 ; i < s . Length ; ++ i ) { String ss = " " ; int count = 0 ; for ( int j = i ; j < s . Length ; ++ j ) { if ( illegal [ s [ j ] ] ) { ++ count ; } ss = ss + s [ j ] ; if ( count <= k ) { us . Add ( ss ) ; } else { break ; } } } return us . Count ; } public static void Main ( ) { String str = " acbacbacaa " ; String anotherStr = " abcdefghijklmnopqrstuvwxyz " ; int k = 2 ; Console . WriteLine ( countSubStrings ( str , anotherStr , k ) ) ; } }