Clear C++ O(n) iterative code borrowed idea from lixx2100's greedy solution with detailed explanation


  • 0
    L

    The greedy idea is simple here. There are basically two cases here but I will use three cases in this post to help you understand these scenarios.

    1. When the smallest letter is on the left-most position, `newString = s[0] + s.substr(1).replace(s[0], '')`
    2. When smallest letter is not on the left-most position:
    	(1): If letters on its left have duplications on its right, e.g.: bc[a]cb, drop all of them. `newString = s[i] + substr(i).replace(s[i], '')`
    	(2): Else, use local smallest as s[i]
    

    You can easily figure out that case 1 and 2(1) are just the same. The code is shown below.

    class Solution {
    public:
        string removeDuplicateLetters(string s) {
            string result = "";
            while (!s.empty()) {
                int count[26] = {0};
                int smallest = 0;
                for (int i = 0; i < s.size(); i++) {
                    char c = s[i];
                    if (c < s[smallest]) {
                        smallest = i;
                    }
                    count[c - 'a']++;
                }
                
                int localSmallest = 0;
                for (int i = 0; i < smallest; i++) {
                    char c = s[i];
                    if (c < s[localSmallest]) {
                        localSmallest = i;
                    }
                    count[c - 'a']--;
                    if (count[c - 'a'] == 0) {
                        smallest = localSmallest;
                        break;
                    }
                }
                
                result += s[smallest];
                
                // Replace all of successive s[smallest] with ''
                string newStr;
                newStr.reserve(s.size() - smallest - 1);
                for (int i = smallest + 1; i < s.size(); i++) {
                    if (s[i] != s[smallest]) {
                        newStr += s[i];
                    }
                }
                
                s = newStr;
            }
            
            return result;
        }
    };
    

    Since there are only 26 letters in English alphabet, the complexity is O(26*n) = O(n).

    Hopefully this post is not too long and can help you understand the algorithm. I personally feel hard to understand those one liner stuffs so I rewrite it in a more understandable fashion.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.