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
< ? php function check ( $ s , $ K ) { for ( $ ch = 0 ; $ ch < 26 ; $ ch ++ ) { $ c = chr ( ord ( ' a ' ) + $ ch ) ; $ last = -1 ; $ found = true ; for ( $ i = 0 ; $ i < $ K ; $ i ++ ) if ( $ s [ $ i ] == $ c ) $ last = $ i ; if ( $ last == -1 ) continue ; for ( $ i = $ K ; $ i < strlen ( $ s ) ; $ i ++ ) { if ( $ s [ $ i ] == $ c ) $ last = $ i ; if ( $ last <= ( $ i - $ K ) ) { $ found = false ; break ; } } if ( $ found ) return 1 ; } return 0 ; } function binarySearch ( $ s ) { $ low = 1 ; $ high = strlen ( $ s ) ; while ( $ low <= $ high ) { $ mid = ( $ high + $ low ) >> 1 ; if ( check ( $ s , $ mid ) ) { $ ans = $ mid ; $ high = $ mid - 1 ; } else $ low = $ mid + 1 ; } return $ ans ; } $ s = " abcde " ; echo binarySearch ( $ s ) . " STRNEWLINE " ; $ s = " aaaa " ; echo binarySearch ( $ s ) . " STRNEWLINE " ; ? >