Maximum non | C ++ program for the above approach ; Function to find maximum distinct character after removing K character ; Freq implemented as hash table to store frequency of each character ; Store frequency of each character ; Insert each frequency in v ; Sort the freq of character in non - decreasing order ; Traverse the vector ; Update v [ i ] and k ; If K is still not 0 ; Store the final answer ; Count this character if freq 1 ; Return count of distinct characters ; Driver Code ; Given string ; Given k ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxDistinctChar ( string s , int n , int k ) { unordered_map < int , int > freq ; for ( int i = 0 ; i < n ; i ++ ) freq [ s [ i ] ] ++ ; vector < int > v ; for ( auto it = freq . begin ( ) ; it != freq . end ( ) ; it ++ ) { v . push_back ( it -> second ) ; } sort ( v . begin ( ) , v . end ( ) ) ; for ( int i = 0 ; i < v . size ( ) ; i ++ ) { int mn = min ( v [ i ] - 1 , k ) ; v [ i ] -= mn ; k -= mn ; } if ( k > 0 ) { for ( int i = 0 ; i < v . size ( ) ; i ++ ) { int mn = min ( v [ i ] , k ) ; v [ i ] -= mn ; k -= mn ; } } int res = 0 ; for ( int i = 0 ; i < v . size ( ) ; i ++ ) if ( v [ i ] == 1 ) res ++ ; return res ; } int main ( ) { string S = " geeksforgeeks " ; int N = S . size ( ) ; int K = 1 ; cout << maxDistinctChar ( S , N , K ) ; return 0 ; }