Intuitive Java solution (3ms)


  • 1
    E
    public class Solution {
        public String removeDuplicateLetters(String s) {
            int[] rem = new int[26];
            for (int i = 0; i < s.length(); i++)
                rem[s.charAt(i) - 'a']++;
            
            boolean[] onStack = new boolean[26];
            char[] a = new char[s.length() + 1];
            int sz = 0;
            for (int i = 0; i < s.length(); i++) {
                rem[s.charAt(i) - 'a']--;
                if (onStack[s.charAt(i) - 'a']) {
                    continue;
                }
                while (sz != 0 && a[sz] >= s.charAt(i) && rem[a[sz] - 'a'] > 0){
                    onStack[a[sz] - 'a'] = false;
                    sz--;
                }
                ++sz;
                a[sz] = s.charAt(i);
                onStack[a[sz] - 'a'] = true;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 1; i <= sz; i++)
                sb.append(a[i]);
            return sb.toString();
        }
    }

Log in to reply
 

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