Minimum K such that every substring of length atleast K contains a character c | Java Program to find minimum K such that every substring of length atleast K contains some 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
class GFG { static int check ( String s , int K ) { for ( int ch = 0 ; ch < 26 ; ch ++ ) { char c = ( char ) ( ' a ' + ch ) ; int last = - 1 ; boolean found = true ; for ( int i = 0 ; i < K ; i ++ ) if ( s . charAt ( i ) == c ) last = i ; if ( last == - 1 ) continue ; for ( int i = K ; i < s . length ( ) ; i ++ ) { if ( s . charAt ( i ) == c ) last = i ; if ( last <= ( i - K ) ) { found = false ; break ; } } if ( found ) return 1 ; } return 0 ; } static int binarySearch ( String s ) { int low = 1 , high = s . length ( ) ; int ans = 0 ; while ( low <= high ) { int mid = ( high + low ) >> 1 ; if ( check ( s , mid ) == 1 ) { ans = mid ; high = mid - 1 ; } else low = mid + 1 ; } return ans ; } public static void main ( String args [ ] ) { String s = " abcde " ; System . out . println ( binarySearch ( s ) ) ; s = " aaaa " ; System . out . println ( binarySearch ( s ) ) ; } }