Java easy to understand accepted O(n) solution.


  • 0
    S

    The idea is that by going through the string, we need to skip current character if we can find smaller character later and also we can find all the character in between after the smaller one because we can not omit any shown character. So it runs the first run to figure out the last seen indices of each character to figure it out.

    public class Solution {
        public String removeDuplicateLetters(String s) {
            int []lastSeen = new int[26]; for (int i = 0; i < 26; i++)  lastSeen[i] = -1;
            boolean []printed = new boolean[26]; for (int i = 0; i < 26; i++)  printed[i] = false;
            
            int n = s.length();
            // first run, mark the last seen position for each character
            for (int i = 0; i < n; i++) {
                lastSeen[s.charAt(i) - 'a'] = i;
            }
    
            // second run        
            StringBuilder str = new StringBuilder();
            int i = 0;
            while (i < n)   {
                char ch = s.charAt(i);
                if (printed[ch - 'a'])  {
                    i++;
                    continue;
                }
                boolean ifJump = false;
                
                for (int j = i; j < n; j++) {
                    int tmpCh = s.charAt(j);
                    // skip already printed characters
                    if (printed[tmpCh - 'a'])   continue;
                    
                    // found a smaller char that has not been printed yet
                    if (tmpCh < ch)  {
                        ifJump = true;
                        i = j;
                        break;
                    }
                    
                    // if a char at j can not be skipped
                    // char at j can not be smaller than char at i, so print the char at i
                    if (lastSeen[tmpCh - 'a'] <= j) break;
                }
                
                if (!ifJump)    {
                    printed[ch - 'a'] = true;
                    str.append(ch);
                    i++;
                }
            }
            
            return str.toString();
        }
    }

Log in to reply
 

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