2025-06-21 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's June LeetCoding Challenge with cpp.

June LeetCoding Challenge 21

Description

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.

Solution

class Solution {
  int tryThis(const vector<int> &count, int target, int k) {
    int result = 0;
    for(auto c : count) {
      if(c < target) result += c;
      else result += max(0, c - target - k);
    }
    return result;
  }
public:
  int minimumDeletions(string word, int k) {
    vector<int> count(26);
    for(auto c : word) {
      count[c - 'a'] += 1;
    }
    sort(count.begin(), count.end());
    int answer = INT_MAX;
    for(int i = 0; i < 26; ++i) {
      answer = min(answer, tryThis(count, count[i], k));
    }
    return answer;
  }
};

// Accepted
// 732/732 cases passed (0 ms)
// Your runtime beats 100 % of cpp submissions
// Your memory usage beats 84.11 % of cpp submissions (19.2 MB)
Algorithm