3085. Minimum Deletions to Make String K-Special Solved using Java !

Darshan — Sat, 21 Jun 2025 13:26:27 +0000

Problem Breakdown:
You're given a string word and an integer k.
A string is k-special if for every pair of characters, the difference in their frequency is at most k.

Formally:
For all characters i and j in the string:

|freq(i) - freq(j)| <= k

🎯 Goal:
Minimize the number of deletions needed to satisfy the above condition.

✅ Approach:
Count frequency of each character.

Try each possible target frequency, say f, from 1 up to the max frequency.

For each target f, ensure that every character has frequency between [f, f + k].

If a character has freq < f or freq > f + k, delete extra characters or all of them.

Return the minimum deletions over all such target frequencies.
`Java

`import java.util.*;

class Solution {
public int minimumDeletions(String word, int k) {
int[] freq = new int[26];
for (char ch : word.toCharArray()) {
freq[ch - 'a']++;
}

    List<Integer> freqs = new ArrayList<>();
    for (int f : freq) {
        if (f > 0) freqs.add(f);
    }

    Collections.sort(freqs);
    int minDeletions = Integer.MAX_VALUE;

    for (int i = 0; i < freqs.size(); i++) {
        int target = freqs.get(i);
        int deletions = 0;

        for (int f : freqs) {
            if (f < target) {
                deletions += f;  // remove all
            } else if (f > target + k) {
                deletions += f - (target + k);
            }
        }

        minDeletions = Math.min(minDeletions, deletions);
    }

    return minDeletions;
}

}

DEV Community: Darshan

3085. Minimum Deletions to Make String K-Special Solved using Java !