feat: add solutions to lc problem: No.1647. Minimum Deletions to Make Character Frequencies Unique

yanglbme · yanglbme · commit 75d71ab8b44e · 2021-07-01T23:42:13.000+08:00
diff --git a/solution/1600-1699/1647.Minimum Deletions to Make Character Frequencies Unique/README.md b/solution/1600-1699/1647.Minimum Deletions to Make Character Frequencies Unique/README.md
@@ -53,7 +53,7 @@
 
 <!-- 这里可写通用的实现逻辑 -->
 
-哈希表 + 升序排序
+哈希表 + 排序。
 
 <!-- tabs:start -->
 
@@ -62,15 +62,41 @@
 <!-- 这里可写当前语言的特殊实现逻辑 -->
 
 ```python
-
+class Solution:
+    def minDeletions(self, s: str) -> int:
+        counter = collections.Counter(s)
+        vals = [v for v in counter.values()]
+        vals.sort(reverse=True)
+        ans = 0
+        for i in range(1, len(vals)):
+            while vals[i] >= vals[i - 1] and vals[i] > 0:
+                vals[i] -= 1
+                ans += 1
+        return ans
 ```
 
 ### **Java**
 
 <!-- 这里可写当前语言的特殊实现逻辑 -->
 
 ```java
-
+class Solution {
+    public int minDeletions(String s) {
+        int[] counter = new int[26];
+        for (char c : s.toCharArray()) {
+            ++counter[c - 'a'];
+        }
+        Arrays.sort(counter);
+        int ans = 0;
+        for (int i = 24; i >= 0; --i) {
+            while (counter[i] >= counter[i + 1] && counter[i] > 0) {
+                --counter[i];
+                ++ans;
+            }
+        }
+        return ans;
+    }
+}
 ```
 
 ### **TypeScript**
diff --git a/solution/1600-1699/1647.Minimum Deletions to Make Character Frequencies Unique/README_EN.md b/solution/1600-1699/1647.Minimum Deletions to Make Character Frequencies Unique/README_EN.md
@@ -52,13 +52,39 @@ Note that we only care about characters that are still in the string at the end
 ### **Python3**
 
 ```python
-
+class Solution:
+    def minDeletions(self, s: str) -> int:
+        counter = collections.Counter(s)
+        vals = [v for v in counter.values()]
+        vals.sort(reverse=True)
+        ans = 0
+        for i in range(1, len(vals)):
+            while vals[i] >= vals[i - 1] and vals[i] > 0:
+                vals[i] -= 1
+                ans += 1
+        return ans
 ```
 
 ### **Java**
 
 ```java
-
+class Solution {
+    public int minDeletions(String s) {
+        int[] counter = new int[26];
+        for (char c : s.toCharArray()) {
+            ++counter[c - 'a'];
+        }
+        Arrays.sort(counter);
+        int ans = 0;
+        for (int i = 24; i >= 0; --i) {
+            while (counter[i] >= counter[i + 1] && counter[i] > 0) {
+                --counter[i];
+                ++ans;
+            }
+        }
+        return ans;
+    }
+}
 ```
 
 ### **TypeScript**
diff --git a/solution/1600-1699/1647.Minimum Deletions to Make Character Frequencies Unique/Solution.java b/solution/1600-1699/1647.Minimum Deletions to Make Character Frequencies Unique/Solution.java
@@ -0,0 +1,17 @@
+class Solution {
+    public int minDeletions(String s) {
+        int[] counter = new int[26];
+        for (char c : s.toCharArray()) {
+            ++counter[c - 'a'];
+        }
+        Arrays.sort(counter);
+        int ans = 0;
+        for (int i = 24; i >= 0; --i) {
+            while (counter[i] >= counter[i + 1] && counter[i] > 0) {
+                --counter[i];
+                ++ans;
+            }
+        }
+        return ans;
+    }
+}
diff --git a/solution/1600-1699/1647.Minimum Deletions to Make Character Frequencies Unique/Solution.py b/solution/1600-1699/1647.Minimum Deletions to Make Character Frequencies Unique/Solution.py
@@ -0,0 +1,11 @@
+class Solution:
+    def minDeletions(self, s: str) -> int:
+        counter = collections.Counter(s)
+        vals = [v for v in counter.values()]
+        vals.sort(reverse=True)
+        ans = 0
+        for i in range(1, len(vals)):
+            while vals[i] >= vals[i - 1] and vals[i] > 0:
+                vals[i] -= 1
+                ans += 1
+        return ans
