Added solution for leet code 1647

anxious-coder-lhs · anxious-coder-lhs · commit 6e5b6d51a5d5 · 2020-11-12T01:52:36.000+05:30
diff --git a/README.md b/README.md
@@ -57,7 +57,7 @@ Happy to accept any contributions to this in any langugage.
 22. [Leet Code 445 - Add Numbers II](https://leetcode.com/problems/add-two-numbers-ii/) | [Solution 1](./level_medium/LeetCode%20445_Add%202%20Numbers_1.ts) | [Solution 2](./level_medium/LeetCode%20445_Add%202%20Numbers_2.ts)
 23. [Leet Code 59 - Spiral Matrix II](https://leetcode.com/problems/spiral-matrix-ii/) | [Solution](level_medium/SpiralMatrixII.ts)
 24. [Leet Code 151 - Reverse Words in a String](https://leetcode.com/problems/reverse-words-in-a-string/) | [Solution](level_medium/LeetCode_151_Reverse_Words_In_a_String.ts)
-
+25. [Leet Code 1647 - Minimum Deletions to Make Character Frequency Unique](https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique/) | [Solution](level_medium/LeetCode_1647_Min_Deletions_For_Unique_Freq.ts)
 
 
 ## Hard
diff --git a/level_medium/LeetCode_1647_Min_Deletions_For_Unique_Freq.ts b/level_medium/LeetCode_1647_Min_Deletions_For_Unique_Freq.ts
@@ -0,0 +1,37 @@
+/**
+ * Leet Code 1647
+ * 
+ * Solution uses the greedy algorithm, since we can only delete characters and not add characters. Since, we can
+ * only delete characters, we can start deleting from any order as far as we are ensuring the unique property.
+ * 
+ * In order to achieve that, we count the frequency of each character. Once, it is done, we keep track of a seen
+ * collection (maintained by the set) which tracks whether a particular frequency has been seen before for any
+ * char. Since, the frequency has to be unique, we need to delete characters, if we find something which is already
+ * existing. If the non-unique frequency is found, we can delete the characters, till we find a unique place for it.
+ * 
+ * Time: O(n) since each char is visited once. Space: O(1) since fixed storage is used.
+ * 
+ * @param s 
+ */
+function minDeletions(s: string): number {
+    
+    // Count Frequency of each character.
+    const freq = Array(26).fill(0)
+    for (let idx = 0; idx < s.length; idx++) 
+        freq[s.charCodeAt(idx) - 97]++
+    
+    
+    // Make necessary deletions to keep the duplicates unique with greedy approach (1st one first).
+    let deletions = 0;
+    const uniqFreq = new Set<number>()
+    for (let idx = 0; idx < 26; idx++) {
+        // Keep deleting the char till we find a frequency of the char which is unique (till now - greedily)
+        while(freq[idx] > 0 && uniqFreq.has(freq[idx])) {
+            deletions++
+            freq[idx]--
+        }
+        uniqFreq.add(freq[idx])
+    }
+    
+    return deletions
+};
