Minimum Deletions for At Most K Distinct Characters

Minimum Deletions for At Most K Distinct Characters - Problem

You are given a string s consisting of lowercase English letters, and an integer k. Your task is to delete some (possibly none) of the characters in the string so that the number of distinct characters in the resulting string is at most k.

Return the minimum number of deletions required to achieve this.

Example: If s = "aabbccdd" and k = 2, you need to keep at most 2 distinct characters. You could keep 'a' and 'b', deleting all 'c' and 'd' characters, requiring 4 deletions.

Input & Output

Example 1 — Basic Case

$ Input: s = "aabbccdd", k = 2

› Output: 4

💡 Note: Keep 2 most frequent characters. All characters appear equally (2 times each), so we can keep any 2 characters like 'a' and 'b', deleting all 'c' and 'd' occurrences = 2 + 2 = 4 deletions.

Example 2 — Different Frequencies

$ Input: s = "aaabbc", k = 2

› Output: 1

💡 Note: Character frequencies: a=3, b=2, c=1. Keep 'a' (3) and 'b' (2), delete 'c' (1). Total deletions = 1.

Example 3 — Edge Case

$ Input: s = "abc", k = 0

› Output: 3

💡 Note: k=0 means we can keep 0 distinct characters, so we must delete all characters = 3 deletions.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters only
0 ≤ k ≤ 26

Visualization

Tap to expand

Understanding the Visualization

Input

String s="aabbccdd" with k=2 distinct characters allowed

Process

Count frequencies and keep k most frequent characters

Output

Minimum deletions needed = 4

Key Takeaway

🎯 Key Insight: To minimize deletions, always keep the k characters that appear most frequently in the string

Asked in

G Google 45 f Facebook 38 a Amazon 32 M Microsoft 28

The key insight is to keep the k most frequently occurring characters and delete all others. Use frequency counting with a hash map or array, then greedily select characters with highest frequencies. Best approach is Frequency Count and Sort with Time: O(d log d), Space: O(d) where d ≤ 26.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2^d × n)	O(d)	Try all possible ways to remove characters and find minimum deletions
Greedy Optimization	O(n)	O(1)	Use counting array for O(1) character access and avoid sorting
Frequency Count and Sort	O(d log d)	O(d)	Count character frequencies, sort by frequency, and keep top k characters

Brute Force - Try All Combinations — Algorithm Steps

Generate all subsets of distinct characters
For each subset with ≤ k characters, count total deletions needed
Return minimum deletions across all valid subsets

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count how many times each character appears

Generate Subsets

Try all possible combinations of characters to keep

Find Minimum

Calculate deletions for each valid subset and return minimum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* s, int k) {
    int len = strlen(s);
    if (k == 0) return len;
    
    int freq[26] = {0};
    for (int i = 0; i < len; i++) {
        freq[s[i] - 'a']++;
    }
    
    char distinctChars[26];
    int distinctCount = 0;
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) {
            distinctChars[distinctCount++] = 'a' + i;
        }
    }
    
    if (distinctCount <= k) return 0;
    
    int minDeletions = len;
    
    // Try all subsets of distinct characters
    for (int mask = 1; mask < (1 << distinctCount); mask++) {
        int bitCount = 0;
        int temp = mask;
        while (temp) {
            bitCount += temp & 1;
            temp >>= 1;
        }
        
        if (bitCount <= k) {
            int keepChars[26] = {0};
            for (int i = 0; i < distinctCount; i++) {
                if (mask & (1 << i)) {
                    keepChars[distinctChars[i] - 'a'] = 1;
                }
            }
            
            int deletions = 0;
            for (int i = 0; i < distinctCount; i++) {
                if (!keepChars[distinctChars[i] - 'a']) {
                    deletions += freq[distinctChars[i] - 'a'];
                }
            }
            if (deletions < minDeletions) {
                minDeletions = deletions;
            }
        }
    }
    
    return minDeletions;
}

int main() {
    char s[1001];
    int k;
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    scanf("%d", &k);
    
    int result = solution(s, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^d × n)

2^d subsets where d is distinct characters, each requiring O(n) to count deletions

✓ Linear Growth

Space Complexity

O(d)

Space to store character frequencies and current subset

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler