Number of substrings with count of each character as k |
function have_same_frequency ( freq , k ) { for ( let i = 0 ; i < 26 ; i ++ ) { if ( freq [ i ] != 0 && freq [ i ] != k ) { return false ; } } return true ; } function count_substrings ( s , k ) { let count = 0 ; let distinct = 0 ; let have = new Array ( 26 ) ; for ( let i = 0 ; i < 26 ; i ++ ) { have [ i ] = false ; } for ( let i = 0 ; i < s . length ; i ++ ) { have [ ( ( s [ i ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ) ) ] = true ; } for ( let i = 0 ; i < 26 ; i ++ ) { if ( have [ i ] ) { distinct ++ ; } } for ( let length = 1 ; length <= distinct ; length ++ ) { let window_length = length * k ; let freq = new Array ( 26 ) ; for ( let i = 0 ; i < 26 ; i ++ ) freq [ i ] = 0 ; let window_start = 0 ; let window_end = window_start + window_length - 1 ; for ( let i = window_start ; i <= Math . min ( window_end , s . length - 1 ) ; i ++ ) { freq [ ( ( s [ i ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ) ) ] ++ ; } while ( window_end < s . length ) { if ( have_same_frequency ( freq , k ) ) { count ++ ; } freq [ ( ( s [ window_start ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ) ) ] -- ; window_start ++ ; window_end ++ ; if ( window_end < s . length ) { freq [ ( s [ window_end ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ) ] ++ ; } } } return count ; } let s = " " ; let k = 2 ; document . write ( count_substrings ( s , k ) + " " ) ; s = " " ; k = 2 ; document . write ( count_substrings ( s , k ) + " " ) ;