New Problem Solution "Remove Duplicate Letters"

haoel · haoel · commit 9c3eac7992c8 · 2017-01-02T15:39:10.000+08:00
diff --git a/README.md b/README.md
@@ -62,6 +62,7 @@ LeetCode
 |322|[Coin Change](https://leetcode.com/problems/coin-change/) | [C++](./algorithms/cpp/coinChange/coinChange.cpp)|Medium|
 |321|[Create Maximum Number](https://leetcode.com/problems/create-maximum-number/) | [C++](./algorithms/cpp/createMaximumNumber/CreateMaximumNumber.cpp)|Hard|
 |319|[Bulb Switcher](https://leetcode.com/problems/bulb-switcher/) | [C++](./algorithms/cpp/bulbSwitcher/bulbSwitcher.cpp)|Medium|
+|316|[Remove Duplicate Letters](https://leetcode.com/problems/remove-duplicate-letters/) | [C++](./algorithms/cpp/removeDuplicateLetters/RemoveDuplicateLetters.cpp)|Hard|
 |315|[Count of Smaller Numbers After Self](https://leetcode.com/problems/count-of-smaller-numbers-after-self/) | [C++](./algorithms/cpp/countOfSmallerNumbersAfterSelf/countOfSmallerNumbersAfterSelf.cpp)|Hard|
 |313|[Super Ugly Number](https://leetcode.com/problems/super-ugly-number/) | [C++](./algorithms/cpp/superUglyNumber/SuperUglyNumber.cpp)|Medium|
 |312|[Burst Balloons](https://leetcode.com/problems/burst-balloons/) | [C++](./algorithms/cpp/burstBalloons/BurstBalloons.cpp)|Hard|
diff --git a/algorithms/cpp/removeDuplicateLetters/RemoveDuplicateLetters.cpp b/algorithms/cpp/removeDuplicateLetters/RemoveDuplicateLetters.cpp
@@ -0,0 +1,52 @@
+// Source : https://leetcode.com/problems/remove-duplicate-letters/
+// Author : Hao Chen
+// Date   : 2017-01-02
+
+/*************************************************************************************** 
+ *
+ * Given a string which contains only lowercase letters, remove duplicate letters so 
+ * that every letter appear once and only once. You must make sure your result is the 
+ * smallest in lexicographical order among all possible results.
+ * 
+ * Example:
+ * 
+ * Given "bcabc"
+ * Return "abc"
+ * 
+ * Given "cbacdcbc"
+ * Return "acdb"
+ * 
+ * Credits:Special thanks to @dietpepsi for adding this problem and creating all test 
+ * cases.
+ ***************************************************************************************/
+
+
+class Solution {
+public:
+    string removeDuplicateLetters(string s) {
+        const int ASCII_LEN = 256;
+        int counter[ASCII_LEN] = {0};
+        bool visited[ASCII_LEN] = {false};
+        
+        for (char ch : s) {
+            counter[ch]++;
+        }
+        
+        string result;
+        for (char ch : s) {
+            counter[ch]--;
+            // if the current `ch` has already put into the result.
+            if (visited[ch]) continue;
+            
+            // if the current `ch` is smaller than the last one char in result.
+            // and we still have duplicated last-one char behind, so we can remove the current one.
+            while ( !result.empty() && ch < result.back() && counter[result.back()] ) {
+                visited[result.back()] = false;
+                result.pop_back();
+            }
+            result.push_back(ch);
+            visited[ch] = true;
+        }
+        return result;
+    }
+};
