Minimum Deletions to Make String K-Special

Minimum Deletions to Make String K-Special - Problem

You are given a string word and an integer k. We consider word to be k-special if |freq(word[i]) - freq(word[j])| <= k for all indices i and j in the string.

Here, freq(x) denotes the frequency of the character x in word, and |y| denotes the absolute value of y.

Return the minimum number of characters you need to delete to make word k-special.

Input & Output

Example 1 — Basic Case

$ Input: word = "aab", k = 0

› Output: 2

💡 Note: Character frequencies: a=2, b=1. Since |2-1|=1 > 0, we need deletions. We can keep only one character type, so minimum deletions = 3-1 = 2.

Example 2 — K-Special Already

$ Input: word = "aabbcc", k = 1

› Output: 0

💡 Note: Character frequencies: a=2, b=2, c=2. All differences are |2-2|=0 ≤ 1, so string is already k-special. No deletions needed.

Example 3 — Larger K

$ Input: word = "aaabbbccc", k = 2

› Output: 0

💡 Note: Character frequencies: a=3, b=3, c=3. All differences are 0 ≤ 2, so no deletions needed.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Count frequency of each character in the string

K-Special Check

Verify all frequency differences are ≤ k

Minimum Deletions

Find optimal way to make string k-special

Key Takeaway

🎯 Key Insight: Find the frequency range that keeps the most characters while satisfying the k-special constraint

Asked in

M Meta 12 G Google 8 A Amazon 6 M Microsoft 4

The key insight is to find the optimal range of character frequencies that minimizes deletions. Count frequencies, sort them, and use sliding window to find the longest valid range where max-min ≤ k. Best approach uses sliding window with Time: O(n + c log c), Space: O(c).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Greedy with Sliding Window	O(n + c log c)	O(c)	Use sliding window on sorted frequencies to find optimal range efficiently
Frequency Count with Greedy Selection	O(n + c²)	O(c)	Count character frequencies, then greedily find optimal frequency range
Brute Force - Try All Combinations	O(2^n)	O(n)	Try all possible ways to delete characters until the string becomes k-special

Optimized Greedy with Sliding Window — Algorithm Steps

Count and sort character frequencies
Use two pointers to maintain sliding window
Expand window while difference ≤ k
Contract window when difference > k
Track maximum characters that can be kept

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Frequencies

Arrange frequencies in ascending order

Sliding Window

Expand/contract window to maintain diff ≤ k

Track Maximum

Keep track of maximum characters in valid window

Code -

solution.c — C

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

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int solution(const char* word, int k) {
    // Count character frequencies
    int freq[26] = {0};
    int len = strlen(word);
    for (int i = 0; i < len; i++) {
        freq[word[i] - 'a']++;
    }
    
    int frequencies[26];
    int count = 0;
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) {
            frequencies[count++] = freq[i];
        }
    }
    
    qsort(frequencies, count, sizeof(int), compare);
    
    if (count == 0) return 0;
    
    // Use sliding window to find optimal range
    int left = 0;
    int maxCharsKept = 0;
    int currentSum = 0;
    
    for (int right = 0; right < count; right++) {
        currentSum += frequencies[right];
        
        // Shrink window while difference > k
        while (frequencies[right] - frequencies[left] > k) {
            currentSum -= frequencies[left];
            left++;
        }
        
        // Update maximum characters we can keep
        if (currentSum > maxCharsKept) {
            maxCharsKept = currentSum;
        }
    }
    
    return len - maxCharsKept;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n + c log c)

O(n) to count frequencies, O(c log c) to sort where c is unique characters

⚡ Linearithmic

Space Complexity

O(c)

Stores frequency count for up to c unique characters

✓ Linear Space

3.2K Views

Medium Frequency

~25 min Avg. Time

147 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

Optimized Greedy with Sliding Window — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler