Minimum K such that every substring of length at least K contains a character c | Set | C ++ program for the above approach ; Function to find minimum value of K such that there exist atleast one K amazing character ; Stores the answer ; Update the string S ; Iterate over the characters in range [ a , z ] ; Stores the last index where c appears ; Stores the maximum possible length ; Update string S ; Iterate over characters of string S ; If S [ i ] is equal to c ; Stores the distance between positions of two same c ; Update max_len ; Update the value of prev ; Update the value of ans ; Return the answer ; Driver Code ; Given Input ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int MinimumLengthSubstring ( string S , int N ) { int ans = N ; S = "0" + S + "0" ; for ( char c = ' a ' ; c <= ' z ' ; ++ c ) { int prev = 0 ; int max_len = 0 ; S [ 0 ] = c ; S [ N + 1 ] = c ; for ( int i = 1 ; i <= N + 1 ; ++ i ) { if ( S [ i ] == c ) { int len = i - prev ; max_len = max ( max_len , len ) ; prev = i ; } } ans = min ( ans , max_len ) ; } return ans ; } int main ( ) { string S = " abcde " ; int N = S . length ( ) ; cout << MinimumLengthSubstring ( S , N ) ; }