aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--min_del_make_str_special.c30
-rw-r--r--min_del_make_str_special.py33
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))