Recursive greedy; Take leftmost for each char, then recurse on its su…

…ffix; Each sweep find the leftmost of the smallest letter encountered
GuanhuiGuan · Jul 17, 2018 · 90e9ac4 · 90e9ac4
1 parent 46e9b67
commit 90e9ac4
Showing 1 changed file with 20 additions and 0 deletions.
diff --git a/Remove Duplicate Letters.java b/Remove Duplicate Letters.java
@@ -0,0 +1,20 @@
+class Solution {
+    public String removeDuplicateLetters(String s) {
+        // Recursion, Greedy
+        // Take the leftmost letter for each character
+        int[] occ = new int[26];
+        for(char c: s.toCharArray()) {
+            occ[c-'a']++;
+        }
+        int index = 0;
+        for(int i = 0; i < s.length(); i++) {
+            // Find the lexical smallest char
+            if(s.charAt(index) > s.charAt(i))   index = i;
+            // Decrement
+            if(--occ[s.charAt(i)-'a'] == 0) break;
+        }
+        // Remove such chars and recurse on the suffix
+        return s.length() == 0? "": s.charAt(index) + 
+            removeDuplicateLetters(s.substring(index+1).replaceAll("" + s.charAt(index), ""));
+    }
+}