Minimum K such that every substring of length atleast K contains a character c | CPP 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int check ( string s , int K ) { for ( int ch = 0 ; ch < 26 ; ch ++ ) { char c = ' a ' + ch ; int last = -1 ; bool found = true ; for ( int i = 0 ; i < K ; i ++ ) if ( s [ i ] == c ) last = i ; if ( last == -1 ) continue ; for ( int i = K ; i < s . size ( ) ; i ++ ) { if ( s [ i ] == c ) last = i ; if ( last <= ( i - K ) ) { found = false ; break ; } } if ( found ) return 1 ; } return 0 ; } int binarySearch ( string s ) { int low = 1 , high = ( int ) s . size ( ) ; int ans ; while ( low <= high ) { int mid = ( high + low ) >> 1 ; if ( check ( s , mid ) ) { ans = mid ; high = mid - 1 ; } else low = mid + 1 ; } return ans ; } int32_t main ( ) { string s = " abcde " ; cout << binarySearch ( s ) << endl ; s = " aaaa " ; cout << binarySearch ( s ) << endl ; return 0 ; }