A short O(n) recursive greedy solution


  • 197
    L

    Given the string s, the greedy choice (i.e., the leftmost letter in the answer) is the smallest s[i], s.t.
    the suffix s[i .. ] contains all the unique letters. (Note that, when there are more than one smallest s[i]'s, we choose the leftmost one. Why? Simply consider the example: "abcacb".)

    After determining the greedy choice s[i], we get a new string s' from s by

    1. removing all letters to the left of s[i],
    2. removing all s[i]'s from s.

    We then recursively solve the problem w.r.t. s'.

    The runtime is O(26 * n) = O(n).

    public class Solution {
        public String removeDuplicateLetters(String s) {
            int[] cnt = new int[26];
            int pos = 0; // the position for the smallest s[i]
            for (int i = 0; i < s.length(); i++) cnt[s.charAt(i) - 'a']++;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) < s.charAt(pos)) pos = i;
                if (--cnt[s.charAt(i) - 'a'] == 0) break;
            }
            return s.length() == 0 ? "" : s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), ""));
        }
    }

  • -8
    W
            /**
             * @param {string} s
             * @return {string}
             */
            var removeDuplicateLetters = function(s) {
                var arr = s.split("");
                arr.sort();
                var tmpstr = "";
                var result = [];
                for(var i = 0; i < arr.length; i++){
                    if(arr[i]!==tmpstr){
                        result.push(arr[i]);
                        tmpstr = arr[i];
                    }else{
                        continue;
                    }
                }
                return result.join("");
            };

  • 15
    C

    The runtime looks like O(n^2) to me :)
    As every time when removeDuplicateLetters is called, it goes through the whole string to collect cnt, and s.substring(j + 1).replaceAll("" + ch, "") is O(n) as well because it runs through the whole string.


  • 23
    L

    Each recursive call takes O(n), but at most 26 recursive calls will be triggered.


  • 3
    C

    That makes sense, the final result is no longer than 26 :) Nice solution!


  • 7
    C

    I really like your solution, this is my Python version of it.

    def removeDuplicateLetters(s):
        idx = lambda c: ord(c) - ord('a')
        cnt = [0] * 26
        for c in s:
            cnt[idx(c)] += 1
            
        candidate = [0] * 26
        for c in s:
            i = idx(c)
            if cnt[i] >= 1:
                candidate[i] = 1
                cnt[i] -= 1
            if cnt[i] == 0:
                break
            
    
        for i in xrange(0, 26):
            if candidate[i]:
                ch = chr(ord('a') + i)
                return ch + removeDuplicateLetters(s[s.find(ch):].replace(ch, ""))
        return ""

  • 0
    L

    I am glad you like it. :)

    I just optimized my code, and it looks even shorter now.


  • 8
    T

    This idea is really smart. Come up with a Ten lines python code:

    def removeDuplicateLetters(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s: return ""
        counts = collections.Counter(list(s))
        
        pos = 0
        for i, x in enumerate(s):
            if x < s[pos]: pos = i
            counts[x] -= 1
            if counts[x] == 0: break
    
        return s[pos] + self.removeDuplicateLetters(s[pos+1:].replace(s[pos], ""))

  • 0
    C

    That's even nicer, it's a shame that I couldn't vote twice :p


  • 6
    Z

    Iterative Version, use '}' to mark elements that we deleted.

    string removeDuplicateLetters(string s) {
            string res;
            int p=0;
            while(p<s.size()){
                vector<int> cnt(256,0);
                for(int i=p; i<s.size(); i++) if(s[i]!='}') cnt[s[i]]++;
                int nxtp=p;
                for(int i=p; i<s.size(); i++){
                    if(s[i]<s[nxtp]) nxtp=i;
                    if(--cnt[s[i]]==0) break; //unique in suffix s[i...]
                }
                for(int j=p; j<s.size(); j++){ 
                    if(j<nxtp || s[j]==s[nxtp] && j>nxtp) s[j]='}';
                }
                while(p<=nxtp || s[p]=='}') p++;
            }
            for(auto c: s) if(c!='}') res.push_back(c);
            return res;
        }

  • 0
    S

    Like your python solution! Especially the lambda way.


  • 1
    A

    Very elegant!
    I have a similar C++ iterative solution using bit manipulation

    class Solution {
    public:
    	string removeDuplicateLetters(string s) {
    		vector<int> masks(s.length(), 0);
    
    		int next = 0;
    		for (int i = s.length() - 1; i >= 0; --i) {
    			int b = (1 << (s[i] - 'a'));
    			if (!(next & b)) {
    				masks[i] = next | b;
    				next = masks[i];
    			}
    			else
    				masks[i] = next;
    		}
    
    		int cnt = setBits(next);
    		int ind = 0;
    		int used = 0;
    		string ret = "";
    		for (; cnt; --cnt) {
    			while (used & (1 << (s[ind] - 'a')))
    				++ind;
    
    			int val = masks[ind] & ~(masks[ind] & used);
    			int best = ind++;
    
    			for (; ind < s.length() && val == (masks[ind] & ~(masks[ind] & used)); ++ind) {
    				int b = 1 << (s[ind] - 'a');
    				if (used & b)
    					continue;
    
    				if (s[ind] < s[best])
    					best = ind;
    			}
    
    			ret += s[best];
    			ind = best + 1;
    			used |= (1 << (s[best] - 'a'));
    		}
    
    		return ret;
    	}
    
    private:
    	int setBits(int n) {
    		int cnt = 0;
    		for (int i = 0; i < 26; ++i)
    			if (n & (1 << i))
    				++cnt;
    		return cnt;
    	}
    };

  • 0
    R

    yes, u are right


  • 0
    D

    cnt was created using "new" and it is not released. Memory leak!


  • 0
    L

    @xuezhou, in Java, one does not need to release the allocated memory explicitly, and the garbage collection is normally handled by JVM.

    In C/C++ instead, an easy way is to replace int[] cnt = new int[26]; by int cnt[26] = {0}; so that the memory will be allocated on the stack, and thus will automatically be released when the function is finished.


  • 0
    D

    yes, you are right.


  • 0
    V

    Recursive looks much cleaner than iterative solution.


  • 0
    L
    This post is deleted!

  • 0
    Z

    just one question: how to understand the line;if (--cnt[s.charAt(i) - 'a'] == 0) break; why you choose to break the loop when --count[s.charAt(i) - 'a' ] ==0 ?


  • 0
    L

    The suffix s[i+1 ..] will no longer contain character s[i], hence no need to proceed any further.


Log in to reply
 

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