text: Number of substrings with count of each character as k |
code: #include <stdbool.h> NEW_LINE #include <stdio.h> NEW_LINE #include <string.h> NEW_LINE int min ( int a , int b ) { return a < b ? a : b ; } bool have_same_frequency ( int freq [ ] , int k ) { for ( int i = 0 ; i < 26 ; i ++ ) { if ( freq [ i ] != 0 && freq [ i ] != k ) { return false ; } } return true ; } int count_substrings ( char * s , int n , int k ) { int count = 0 ; int distinct = 0 ; bool have [ 26 ] = { false } ; for ( int i = 0 ; i < n ; i ++ ) { have [ s [ i ] - ' a ' ] = true ; } for ( int i = 0 ; i < 26 ; i ++ ) { if ( have [ i ] ) { distinct ++ ; } } for ( int length = 1 ; length <= distinct ; length ++ ) { int window_length = length * k ; int freq [ 26 ] = { 0 } ; int window_start = 0 ; int window_end = window_start + window_length - 1 ; for ( int i = window_start ; i <= min ( window_end , n - 1 ) ; i ++ ) { freq [ s [ i ] - ' a ' ] ++ ; } while ( window_end < n ) { if ( have_same_frequency ( freq , k ) ) { count ++ ; } freq [ s [ window_start ] - ' a ' ] -- ; window_start ++ ; window_end ++ ; if ( window_end < n ) { freq [ s [ window_end ] - ' a ' ] ++ ; } } } return count ; } int main ( ) { char * s = " aabbcc " ; int k = 2 ; printf ( " % d STRNEWLINE " , count_substrings ( s , 6 , k ) ) ; s = " aabbc " ; k = 2 ; printf ( " % d STRNEWLINE " , count_substrings ( s , 5 , k ) ) ; return 0 ; }