Easy to understand iterative Java solution


  • 115
    W

    The basic idea is to find out the smallest result letter by letter (one letter at a time). Here is the thinking process for input "cbacdcbc":

    1. find out the last appeared position for each letter;
      c - 7
      b - 6
      a - 2
      d - 4
    2. find out the smallest index from the map in step 1 (a - 2);
    3. the first letter in the final result must be the smallest letter from index 0 to index 2;
    4. repeat step 2 to 3 to find out remaining letters.
    • the smallest letter from index 0 to index 2: a
    • the smallest letter from index 3 to index 4: c
    • the smallest letter from index 4 to index 4: d
    • the smallest letter from index 5 to index 6: b

    so the result is "acdb"

    Notes:

    • after one letter is determined in step 3, it need to be removed from the "last appeared position map", and the same letter should be ignored in the following steps
    • in step 3, the beginning index of the search range should be the index of previous determined letter plus one

    public class Solution {
    
        public String removeDuplicateLetters(String s) {
            if (s == null || s.length() <= 1) return s;
    
            Map<Character, Integer> lastPosMap = new HashMap<>();
            for (int i = 0; i < s.length(); i++) {
                lastPosMap.put(s.charAt(i), i);
            }
    
            char[] result = new char[lastPosMap.size()];
            int begin = 0, end = findMinLastPos(lastPosMap);
    
            for (int i = 0; i < result.length; i++) {
                char minChar = 'z' + 1;
                for (int k = begin; k <= end; k++) {
                    if (lastPosMap.containsKey(s.charAt(k)) && s.charAt(k) < minChar) {
                        minChar = s.charAt(k);
                        begin = k+1;
                    }
                }
    
                result[i] = minChar;
                if (i == result.length-1) break;
    
                lastPosMap.remove(minChar);
                if (s.charAt(end) == minChar) end = findMinLastPos(lastPosMap);
            }
    
            return new String(result);
        }
    
        private int findMinLastPos(Map<Character, Integer> lastPosMap) {
            if (lastPosMap == null || lastPosMap.isEmpty()) return -1;
            int minLastPos = Integer.MAX_VALUE;
            for (int lastPos : lastPosMap.values()) {
                 minLastPos = Math.min(minLastPos, lastPos);
            }
            return minLastPos;
        }
    
    }

  • 0
    E

    Great idea!!!


  • 33
    S

    It's not easy to understand at all.


  • 2
    M

    Clever way of thinking!
    Wouldn't it be better if you can use an integer array of size 26 instead of Map to store positioning information? Use Arrays.fill(array, -1) to separate the chars that does not appear at all from others.


  • 0
    M

    Easy to understand and nice explanation.


  • 0
    C

    easy to understand,thank you very much.


  • 0
    S

    Nice solution. My 2 cents is this case we know that the string only contains lower case alphabet, so you don't need to use the map.


  • 3
    V

    great , your solution might not be the fastest, but definitely the easiest to understand (for me at least). Much better than those "concise" solutions without any explanation.


  • 0
    S

    what is the complexity of this algorithm?


  • 0

    After comparing my stack solution with others, I found your solution is in another perspective which is very interesting.


  • 4

    @WHJ425 Rewrite your code:

    public class Solution {
        public String removeDuplicateLetters(String s) {
            char[] array = s.toCharArray();
            HashMap<Character, Integer> map = new HashMap<Character, Integer>();
            for (int i = 0; i < array.length; i++) {
                char c = array[i];
                map.put(c, i);
            }
            char[] result = new char[map.size()];
            int start = 0;
            for (int i = 0; i < result.length; i++) {
                int end = findMinPos(map);
                char min = 'z' + 1;
                for (int j = start; j <= end; j++) {
                    if (map.containsKey(array[j]) && array[j] < min) {
                        min = array[j];
                        start = j + 1;
                    }
                }
                result[i] = min;
                map.remove(min);
            }
            
            return String.valueOf(result);
        }
        
        private int findMinPos(HashMap<Character, Integer> map) {
            int pos = Integer.MAX_VALUE;
            for (Integer end : map.values()) {
                pos = Math.min(pos, end);
            }
            return pos;
        }
    }
    

  • 0
    N

    The worst case complexity is O(nm) with m is the size of the alphabet. Correct me if I am wrong.


  • 0
    J
    This post is deleted!

  • 0
    M
    This post is deleted!

  • 0
    B

    My C++ code, your idea ^_^ ! The idea is really great!

    class Solution {
    public: 
        typedef pair<int, char>p;
        string removeDuplicateLetters(string s) {
            string ans;
            stack<int>st;
            int len = s.length();
            vector<int>vis1(26, 0);
            vector<int>vis(26, 0);
            for(int i = len - 1; i >= 0; --i){
                if(vis1[s[i] - 'a']) continue;
                vis1[s[i] - 'a'] = 1;
                st.push(i);
            }
            int sta = 0;
            while(!st.empty()){
                while(!st.empty() && vis[s[st.top()] - 'a']){
                    st.pop();
                    continue;
                }
                if(st.empty()) break;
                int ed = st.top();
                int pos = -1;
                for(int i = sta; i <= ed; ++i){
                    if(vis[s[i] - 'a']) continue;
                    if(pos == -1 || s[pos] > s[i] ) pos = i;
                }
                sta = pos + 1;
                if(s[pos] == s[ed]) st.pop();
                ans += s[pos];
                vis[s[pos] - 'a'] = 1;
            }
            return ans;
        }
    };
    

  • 0
    T
    This post is deleted!

  • 0

    @namxh

    m is at most 26. So it is O(n) time complexity.


  • 0

    @WHJ425
    Thanks for you sharing your nice solution. At first, I came up with a similar idea with you. But I can figure out how to implement. I rewrite your solution in C++ to make it more concise.

    class Solution {
        int findMinIndex(const unordered_map<char, int>& char_idx) {
            int idx = INT_MAX;
            for (const auto& pa: char_idx) {
                idx = min(idx, pa.second);
            }
            return idx;
        }
    public:
        string removeDuplicateLetters(string s) {
            unordered_map<char, int> char_idx;
            // keep the last index of each char
            for (int i = 0; i < s.size(); ++i) {
                char_idx[s[i]] = i;
            }
            
            string res;
            int beg = 0;
            // if we have char to add
            while (!char_idx.empty()) {
                int end = findMinIndex(char_idx);
                char c = CHAR_MAX;
                for (int i = beg; i <= end;  ++i) {
                    //  find the minimun char in s[beg:end], this char should be in our map
                    if (s[i] < c && char_idx.find(s[i]) != char_idx.end()) {
                        c = s[i];
                        beg = i + 1;
                    }
                }
                // erase current char from our map
                char_idx.erase(c);
                res.push_back(c);
            }
            
            return res;
        }
    };
    

Log in to reply
 

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