Maximum length prefix such that frequency of each character is atmost number of characters with minimum frequency | C ++ implementation to find the prefix of the s such that occurrence of each character is atmost the count of minimum frequency in the s ; Function to find the maximum possible prefix of the s ; Hash map to store the frequency of the characters in the s ; Iterate over the s to find the occurence of each Character ; Minimum frequency of the Characters ; Loop to find the count of minimum frequency in the hash - map ; Loop to find the maximum possible length of the prefix in the s ; Condition to check if the frequency is greater than minimum possible freq ; maxprefix s and its length . ; Driver code ; s is initialize . ; str is passed in MaxPrefix function .
#include <bits/stdc++.h> NEW_LINE using namespace std ; void MaxPrefix ( string s ) { map < char , int > Dict ; for ( char i : s ) { Dict [ i ] ++ ; } int minfrequency = INT_MAX ; for ( auto x : Dict ) { minfrequency = min ( minfrequency , x . second ) ; } int countminFrequency = 0 ; for ( auto x : Dict ) { if ( x . second == minfrequency ) countminFrequency += 1 ; } map < char , int > mapper ; int indi = 0 ; for ( char i : s ) { mapper [ i ] += 1 ; if ( mapper [ i ] > countminFrequency ) break ; indi += 1 ; } cout << ( s . substr ( 0 , indi ) ) ; } int main ( ) { string str = " aabcdaab " ; MaxPrefix ( str ) ; }