Minimum K such that every substring of length atleast K contains a character c | This function checks if there exists some character which appears in all K length substrings ; Iterate over all possible characters ; stores the last occurrence ; set answer as true ; ; No occurrence found of current character in first substring of length K ; Check for every last substring of length K where last occurr - ence exists in substring ; If last occ is not present in substring ; current character is K amazing ; This function performs binary search over the answer to minimise it ; Check if answer is found try to minimise it ; Driver Code to test above functions
function check ( s , K ) { for ( var ch = 0 ; ch < 26 ; ch ++ ) { var c = String . fromCharCode ( ' ' . charCodeAt ( 0 ) + ch ) ; var last = - 1 ; var found = true ; for ( var i = 0 ; i < K ; i ++ ) if ( s [ i ] == c ) last = i ; if ( last == - 1 ) continue ; for ( var i = K ; i < s . length ; i ++ ) { if ( s [ i ] == c ) last = i ; if ( last <= ( i - K ) ) { found = false ; break ; } } if ( found ) return 1 ; } return 0 ; } function binarySearch ( s ) { var low = 1 , high = s . length ; var ans ; while ( low <= high ) { var mid = ( high + low ) >> 1 ; if ( check ( s , mid ) ) { ans = mid ; high = mid - 1 ; } else low = mid + 1 ; } return ans ; } var s = " " ; document . write ( binarySearch ( s ) + " " ) ; s = " " ; document . write ( binarySearch ( s ) ) ;