Count distinct substrings that contain some characters at most k times | Java 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
import java . util . * ; class GFG { static int MAX_CHAR = 256 ; static int countSubStrings ( String s , String anotherStr , int k ) { boolean illegal [ ] = new boolean [ MAX_CHAR ] ; for ( int i = 0 ; i < anotherStr . length ( ) ; i ++ ) { illegal [ anotherStr . charAt ( 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 . charAt ( j ) ] ) { ++ count ; } ss = ss + s . charAt ( j ) ; if ( count <= k ) { us . add ( ss ) ; } else { break ; } } } return us . size ( ) ; } public static void main ( String [ ] args ) { String str = " acbacbacaa " ; String anotherStr = " abcdefghijklmnopqrstuvwxyz " ; int k = 2 ; System . out . println ( countSubStrings ( str , anotherStr , k ) ) ; } }