diff options
author | Jack Sangdahl <[email protected]> | 2025-06-20 23:27:41 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-06-20 23:27:41 -0600 |
commit | ab3ffb04a9356621bf2ed0e535054095e27d312d (patch) | |
tree | 6cd68af1f3dd07f76bcbee6ad661f855c5893cc2 | |
parent | a032c2f9c7e06b0402ba2675f96830a0bf80b71e (diff) | |
download | leetcode-ab3ffb04a9356621bf2ed0e535054095e27d312d.tar.gz leetcode-ab3ffb04a9356621bf2ed0e535054095e27d312d.zip |
3085. minimum deletions to make string k-special
-rw-r--r-- | min_del_make_str_special.c | 30 | ||||
-rw-r--r-- | min_del_make_str_special.py | 33 |
2 files changed, 63 insertions, 0 deletions
diff --git a/min_del_make_str_special.c b/min_del_make_str_special.c new file mode 100644 index 0000000..cdac8f0 --- /dev/null +++ b/min_del_make_str_special.c @@ -0,0 +1,30 @@ +// 3085. Minimum Deletions to Make String K-Special +#include "leetcode.h" + +/* + * 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 the 'word'. and '|y|' denotes the absolute value of 'y'. return the + * minimum number of characters you need to delete to make 'word' k-special. + */ + +int minimumDeletions(char *word, int k) { + int freq[26] = {0}, n = strlen(word), ans = INT_MAX; + for (int i = 0; i < n; i++) + freq[word[i] - 'a']++; + for (int i = 0; i < 26; i++) { + int curr = 0; + for (int j = 0; j < 26; j++) + curr += (freq[j] < freq[i]) ? freq[j] : fmax(0, freq[j] - (freq[i] + k)); + ans = fmin(ans, curr); + } + return ans; +} + +int main() { + char *w1 = "aabcaba", *w2 = "dabdcbdcdcd", *w3 = "aaabaaa"; + printf("%d\n", minimumDeletions(w1, 0)); // expect: 3 + printf("%d\n", minimumDeletions(w2, 2)); // expect: 2 + printf("%d\n", minimumDeletions(w3, 2)); // expect: 1 +} diff --git a/min_del_make_str_special.py b/min_del_make_str_special.py new file mode 100644 index 0000000..32c66e0 --- /dev/null +++ b/min_del_make_str_special.py @@ -0,0 +1,33 @@ +# 3085. Minimum Deletions to Make String K-Special +from collections import Counter + +""" +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 the 'word'. and '|y|' denotes the absolute value of 'y'. return the +minimum number of characters you need to delete to make 'word' k-special. +""" + + +class Solution(object): + def minimumDeletions(self, word, k): + """ + :type word: str + :type k: int + :rtype: int + """ + freq, ans = Counter(word).values(), float("inf") + for i in freq: + curr = 0 + for j in freq: + curr += j if j < i else max(0, j - (i + k)) + ans = min(ans, curr) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.minimumDeletions(word="aabcaba", k=0)) + print(obj.minimumDeletions(word="dabdcbdcdcd", k=2)) + print(obj.minimumDeletions(word="aaabaaa", k=2)) |