3085. Minimum Deletions to Make String K-Special LeetCode Solution

In this guide, you will get 3085. Minimum Deletions to Make String K-Special LeetCode Solution with the best time and space complexity. The solution to Minimum Deletions to Make String K-Special problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Deletions to Make String K-Special solution in C++
Minimum Deletions to Make String K-Special solution in Java
Minimum Deletions to Make String K-Special solution in Python
Additional Resources

3085. Minimum Deletions to Make String K-Special LeetCode Solution image

Problem Statement of Minimum Deletions to Make String K-Special

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.

Example 1:

Input: word = “aabcaba”, k = 0
Output: 3
Explanation: We can make word 0-special by deleting 2 occurrences of “a” and 1 occurrence of “c”. Therefore, word becomes equal to “baba” where freq(‘a’) == freq(‘b’) == 2.

Example 2:

Input: word = “dabdcbdcdcd”, k = 2
Output: 2
Explanation: We can make word 2-special by deleting 1 occurrence of “a” and 1 occurrence of “d”. Therefore, word becomes equal to “bdcbdcdcd” where freq(‘b’) == 2, freq(‘c’) == 3, and freq(‘d’) == 4.

Example 3:

Input: word = “aaabaaa”, k = 2
Output: 1
Explanation: We can make word 2-special by deleting 1 occurrence of “b”. Therefore, word becomes equal to “aaaaaa” where each letter’s frequency is now uniformly 6.

Constraints:

1 <= word.length <= 105
0 <= k <= 105
word consists only of lowercase English letters.

Complexity Analysis

Time Complexity: O(n + 26^2) = O(n)
Space Complexity: O(26) = O(1)

3085. Minimum Deletions to Make String K-Special LeetCode Solution in C++

class Solution {
 public:
  int minimumDeletions(string word, int k) {
    int ans = INT_MAX;
    vector<int> count(26);

    for (const char c : word)
      ++count[c - 'a'];

    for (const int minFreq : count) {
      int deletions = 0;
      for (const int freq : count)
        if (freq < minFreq)  // Delete all the letters with smaller frequency.
          deletions += freq;
        else  // Delete letters with exceeding frequency.
          deletions += max(0, freq - (minFreq + k));
      ans = min(ans, deletions);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

3085. Minimum Deletions to Make String K-Special LeetCode Solution in Java

class Solution {
  public int minimumDeletions(String word, int k) {
    int ans = Integer.MAX_VALUE;
    int count[] = new int[26];

    for (final char c : word.toCharArray())
      ++count[c - 'a'];

    for (final int minFreq : count) {
      int deletions = 0;
      for (final int freq : count)
        if (freq < minFreq) // Delete all the letters with smaller frequency.
          deletions += freq;
        else // Delete letters with exceeding frequency.
          deletions += Math.max(0, freq - (minFreq + k));
      ans = Math.min(ans, deletions);
    }

    return ans;
  }
}
// code provided by PROGIEZ

3085. Minimum Deletions to Make String K-Special LeetCode Solution in Python

class Solution:
  def minimumDeletions(self, word: str, k: int) -> int:
    ans = math.inf
    count = collections.Counter(word)

    for minFreq in count.values():
      deletions = 0
      for freq in count.values():
        if freq < minFreq:
          deletions += freq
        else:
          deletions += max(0, freq - (minFreq + k))
      ans = min(ans, deletions)

    return ans
 # code by PROGIEZ