LeetCode 3085 | Medium | Greedy + Frequency Analysis
🧠 Problem Summary
You are given:
- A string
wordconsisting 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 thanxcompletely.
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! 🚀