Count of substrings of length K with exactly K distinct characters | Java program to find the count of k length substrings with k distinct characters using sliding window ; Function to return the required count of substrings ; Store the count ; Store the count of distinct characters in every window ; Store the frequency of the first K length substring ; Increase frequency of i - th character ; If K distinct characters exist ; Traverse the rest of the substring ; Increase the frequency of the last character of the current substring ; Decrease the frequency of the first character of the previous substring ; If the character is not present in the current substring ; If the count of distinct characters is 0 ; Return the count ; Driver code ; string str ; integer K ; Print the count of K length substrings with k distinct characters
import java . util . * ; class GFG { public static int countSubstrings ( String str , int K ) { int N = str . length ( ) ; int answer = 0 ; Map < Character , Integer > map = new HashMap < Character , Integer > ( ) ; for ( int i = 0 ; i < K ; i ++ ) { if ( map . get ( str . charAt ( i ) ) == null ) { map . put ( str . charAt ( i ) , 1 ) ; } else { map . put ( str . charAt ( i ) , map . get ( str . charAt ( i ) ) + 1 ) ; } } if ( map . size ( ) == K ) answer ++ ; for ( int i = K ; i < N ; i ++ ) { if ( map . get ( str . charAt ( i ) ) == null ) { map . put ( str . charAt ( i ) , 1 ) ; } else { map . put ( str . charAt ( i ) , map . get ( str . charAt ( i ) ) + 1 ) ; } map . put ( str . charAt ( i - K ) , map . get ( str . charAt ( i - K ) ) - 1 ) ; if ( map . get ( str . charAt ( i - K ) ) == 0 ) { map . remove ( str . charAt ( i - K ) ) ; } if ( map . size ( ) == K ) { answer ++ ; } } return answer ; } public static void main ( String [ ] args ) { String str = " aabcdabbcdc " ; int K = 3 ; System . out . println ( countSubstrings ( str , K ) ) ; } }