🎴 Beginner-Friendly Guide "Minimum Deletions to Make String K-Special" LeetCode 3085 (C++ | Python

LeetCode 3085 | Medium | Greedy + Frequency Analysis

🧠 Problem Summary

You are given:

A string word consisting of lowercase letters.
An integer k.

A string is k-special if for every pair of characters i, j in the string:

|freq(word[i]) - freq(word[j])| <= k

Your task is to minimize the number of deletions required to make word k-special.

🧹 Intuition

To make a string k-special, the difference between the maximum and minimum frequency of any two letters should be ≤ k.

Key Observations:

Count the frequency of each character.
Try to normalize frequencies around every possible frequency value.
For each candidate frequency x, adjust higher values to be ≤ x + k, and remove characters with frequency less than x completely.

This problem becomes a greedy scan over frequency values to find the configuration with minimal deletions.

🧮 C++ Code

class Solution {
public:
    int minimumDeletions(string word, int k) {
        vector<int> freq(26, 0);
        for (char ch : word)
            freq[ch - 'a']++;

        sort(freq.begin(), freq.end());

        int ans = 1e5 + 5;
        int i = 0;
        while (freq[i] == 0) i++;  // Skip zeros
        int t = i;

        for (; i < 26; i++) {
            int x = freq[i];
            int ops = 0;
            for (int j = t; j < 26; j++) {
                if (i == j) continue;
                int y = freq[j];
                if (y - x > k) ops += y - x - k;
                if (y < x) ops += y;
            }
            ans = min(ans, ops);
        }

        return ans;
    }
};

📝 Key Notes:

Frequencies are sorted for easier range-based analysis.
Try making every valid freq[i] the base frequency.
If any frequency is too large, trim it down; if too small, delete it.
Time Complexity: O(26^2) ~= O(1)
Space Complexity: O(26)

💻 JavaScript Code

var minimumDeletions = function(word, k) {
    const freq = Array(26).fill(0);
    for (const ch of word)
        freq[ch.charCodeAt(0) - 'a'.charCodeAt(0)]++;

    freq.sort((a, b) => a - b);
    let ans = 1e5 + 5;
    let i = 0;
    while (freq[i] === 0) i++;
    let t = i;

    for (; i < 26; i++) {
        let x = freq[i], ops = 0;
        for (let j = t; j < 26; j++) {
            if (i === j) continue;
            let y = freq[j];
            if (y - x > k) ops += y - x - k;
            if (y < x) ops += y;
        }
        ans = Math.min(ans, ops);
    }
    return ans;
};

🐍 Python Code

class Solution:
    def minimumDeletions(self, word: str, k: int) -> int:
        freq = [0] * 26
        for ch in word:
            freq[ord(ch) - ord('a')] += 1

        freq.sort()
        i = 0
        while i < 26 and freq[i] == 0:
            i += 1
        t = i
        ans = float('inf')

        for i in range(t, 26):
            x = freq[i]
            ops = 0
            for j in range(t, 26):
                if i == j:
                    continue
                y = freq[j]
                if y - x > k:
                    ops += y - x - k
                if y < x:
                    ops += y
            ans = min(ans, ops)

        return ans

✅ Final Thoughts

This problem highlights:

The power of frequency analysis and greedy optimization.
How to turn a "global condition" (equalizing freq) into a local transformation via range loops.

Great practice for:

Frequency array manipulation
Greedy analysis on sorted data

Drop a ❤️ if this helped, and stay tuned for more algorithm insights and optimizations!

Happy coding! 🚀

Om Shree @om_shree_0709