Delete the fewest characters so the remaining string becomes k-special, meaning the frequencies of any two distinct characters differ by at most k.
Problem
You are given a string s and an integer k.
A string is called k-special if, for every pair of distinct characters that appear in the string, the difference between their frequencies is at most k.
In one operation, you may delete any single character from s.
Return the minimum number of deletions needed to make s k-special.
Intuition
You may keep some characters and reduce the frequencies of others by deleting characters. The goal is to make all remaining character counts cluster within a range of size k.
Input Format
- A string
s - An integer
k
Output Format
- Return an integer: the minimum number of deletions required.
Constraints
1 <= s.length <= $10^{5}$0 <= k <= $10^{5}$sconsists of lowercase English letters
Hints
- Count how many times each character appears.
- Consider choosing a target minimum frequency among the characters you keep.
- For a fixed target range, characters outside the range can be fully removed or trimmed down.
Input Format
s: lowercase English stringk: non-negative integer
Output Format
- Integer minimum deletions needed
Constraints
1 <= s.length <= $10^{5}$0 <= k <= $10^{5}$scontains only lowercase English letters
Example 1
Input
s = "aabcdd", k = 1
Output
1
Explanation
For the standard k-special definition, the string is already k-special, so the minimum deletions is 0.
Example 2
Input
s = "aaabbbbcc", k = 0
Output
4
Explanation
Frequencies are a:3, b:4, c:2. Since k = 0, all remaining characters must have equal frequency. Keeping frequency 3 for a and b means deleting 1 from b and 2 from c, for a total of 3. Keeping frequency 2 gives 1 + 2 = 3 deletions as well. A minimum of 3 deletions is needed.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.