Given a string S containing lowercase English alphabets of length N and an integer K such that K ? N. The task is to find the maximum number of non-repeating characters after removing K characters from the string.
Examples:
Input: S = “neveropen”, K = 3
Output: 6
Explanation:
Remove 1 occurrences of each g, k and s so the final string is “neveropenforee” and the 6 distinct elements are g, k, s, f, o and rInput: S = “aabbccddeeffgghh”, k = 1
Output: 1
Explanation:
Remove 1 occurrences of any character we will have only one character which will non repeating.
Naive Approach: The naive idea is to delete all possible K characters among the given string and then find the non-repeating characters in all the formed string. Print the maximum among all the count of non-repeating characters.
Time Complexity: O(N!), where N is the length of the given string.
Auxiliary Space: O(N-K)
Efficient Approach: To optimize the above approach,
The idea is to delete K characters in increasing order of frequency whose frequency is at least 2 to get the count of maximum non-repeating characters.
Below are the steps:
- Create a hash table to store the frequency of each element.
- Insert the frequency of each element in a vector V and sort the vector V in increasing order.
- For each element(say currentElement) of vector V find the minimum among K and currentElement – 1 and decrease both K and V[i] by the minimum of the two.
- Repeat the above step until K is non-zero.
- The count of 1s in vector V gives the maximum number of non-repeating characters after deleting K characters.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find maximum distinct// character after removing K characterint maxDistinctChar(string s, int n, int k){ // Freq implemented as hash table to // store frequency of each character unordered_map<int, int> freq; // Store frequency of each character for (int i = 0; i < n; i++) freq[s[i]]++; vector<int> v; // Insert each frequency in v for (auto it = freq.begin(); it != freq.end(); it++) { v.push_back(it->second); } // Sort the freq of character in // non-decreasing order sort(v.begin(), v.end()); // Traverse the vector for (int i = 0; i < v.size(); i++) { int mn = min(v[i] - 1, k); // Update v[i] and k v[i] -= mn; k -= mn; } // If K is still not 0 if (k > 0) { for (int i = 0; i < v.size(); i++) { int mn = min(v[i], k); v[i] -= mn; k -= mn; } } // Store the final answer int res = 0; for (int i = 0; i < v.size(); i++) // Count this character if freq 1 if (v[i] == 1) res++; // Return count of distinct characters return res;}// Driver Codeint main(){ // Given string string S = "neveropen"; int N = S.size(); // Given k int K = 1; // Function Call cout << maxDistinctChar(S, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find maximum distinct// character after removing K characterstatic int maxDistinctChar(char []s, int n, int k){ // Freq implemented as hash table to // store frequency of each character HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>(); // Store frequency of each character for (int i = 0; i < n; i++) { if(freq.containsKey((int)s[i])) { freq.put((int)s[i], freq.get((int)s[i]) + 1); } else { freq.put((int)s[i], 1); } } Vector<Integer> v = new Vector<Integer>(); // Insert each frequency in v for (Map.Entry<Integer, Integer> it : freq.entrySet()) { v.add(it.getValue()); } // Sort the freq of character in // non-decreasing order Collections.sort(v); // Traverse the vector for (int i = 0; i < v.size(); i++) { int mn = Math.min(v.get(i) - 1, k); // Update v[i] and k v.set(i, v.get(i) - mn); k -= mn; } // If K is still not 0 if (k > 0) { for (int i = 0; i < v.size(); i++) { int mn = Math.min(v.get(i), k); v.set(i, v.get(i) - mn); k -= mn; } } // Store the final answer int res = 0; for (int i = 0; i < v.size(); i++) // Count this character if freq 1 if (v.get(i) == 1) res++; // Return count of distinct characters return res;}// Driver Codepublic static void main(String[] args){ // Given String String S = "neveropen"; int N = S.length(); // Given k int K = 1; // Function Call System.out.print(maxDistinctChar(S.toCharArray(), N, K));}}// This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approachfrom collections import defaultdict# Function to find maximum distinct# character after removing K characterdef maxDistinctChar(s, n, k): # Freq implemented as hash table to # store frequency of each character freq = defaultdict (int) # Store frequency of each character for i in range (n): freq[s[i]] += 1 v = [] # Insert each frequency in v for it in freq.values(): v.append(it) # Sort the freq of character in # non-decreasing order v.sort() # Traverse the vector for i in range (len(v)): mn = min(v[i] - 1, k) # Update v[i] and k v[i] -= mn k -= mn # If K is still not 0 if (k > 0): for i in range (len(v)): mn = min(v[i], k); v[i] -= mn k -= mn # Store the final answer res = 0 for i in range (len(v)): # Count this character if freq 1 if (v[i] == 1): res += 1 # Return count of distinct characters return res# Driver Codeif __name__ == "__main__": # Given string S = "neveropen" N = len(S) # Given k K = 1 # Function Call print(maxDistinctChar(S, N, K))# This code is contributed by Chitranayal |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find maximum distinct// character after removing K characterstatic int maxDistinctChar(char []s, int n, int k){ // Freq implemented as hash table to // store frequency of each character Dictionary<int, int> freq = new Dictionary<int, int>(); // Store frequency of each character for(int i = 0; i < n; i++) { if(freq.ContainsKey((int)s[i])) { freq[(int)s[i]] = freq[(int)s[i]] + 1; } else { freq.Add((int)s[i], 1); } } List<int> v = new List<int>(); // Insert each frequency in v foreach(KeyValuePair<int, int> it in freq) { v.Add(it.Value); } // Sort the freq of character in // non-decreasing order v.Sort(); // Traverse the vector for(int i = 0; i < v.Count; i++) { int mn = Math.Min(v[i] - 1, k); // Update v[i] and k v[i] = v[i] - mn; k -= mn; } // If K is still not 0 if (k > 0) { for(int i = 0; i < v.Count; i++) { int mn = Math.Min(v[i], k); v[i] = v[i] - mn; k -= mn; } } // Store the readonly answer int res = 0; for(int i = 0; i < v.Count; i++) // Count this character if freq 1 if (v[i] == 1) res++; // Return count of distinct characters return res;}// Driver Codepublic static void Main(String[] args){ // Given String String S = "neveropen"; int N = S.Length; // Given k int K = 1; // Function call Console.Write(maxDistinctChar(S.ToCharArray(), N, K));}}// This code is contributed by Amit Katiyar |
Javascript
<script>// JavaScript program for the above approach// Function to find maximum distinct// character after removing K characterfunction maxDistinctChar(s, n, k){ // Freq implemented as hash table to // store frequency of each character var freq = new Map(); // Store frequency of each character for (var i = 0; i < n; i++) { if(freq.has(s[i])) freq.set(s[i], freq.get(s[i])+1) else freq.set(s[i], 1) } var v = []; // Insert each frequency in v freq.forEach((value,key) => { v.push(value); }); // Sort the freq of character in // non-decreasing order v.sort() // Traverse the vector for (var i = 0; i < v.length; i++) { var mn = Math.min(v[i] - 1, k); // Update v[i] and k v[i] -= mn; k -= mn; } // If K is still not 0 if (k > 0) { for (var i = 0; i < v.length; i++) { var mn = Math.min(v[i], k); v[i] -= mn; k -= mn; } } // Store the final answer var res = 0; for (var i = 0; i < v.length; i++) // Count this character if freq 1 if (v[i] == 1) res++; // Return count of distinct characters return res;}// Driver Code// Given stringvar S = "neveropen";var N = S.length;// Given kvar K = 1;// Function Calldocument.write( maxDistinctChar(S, N, K));</script> |
Output:
4
Time Complexity: O(N)
Auxiliary Space: O(26)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
