Java O(n) iterative greedy solution


  • 10
    Y

    I used StringBuilder to build the solution. First we count all the characters in the string, and then when we iterate the string, when we see a smaller char than the previous one, we greedily remove the previous ones as long as there are still same chars later. A visited array is used to make sure than we only take same character to the left because we want the lexi smallest sequence.

    public class Solution {
        public String removeDuplicateLetters(String s) {
            int[] count = new int[26];
            char[] chars = s.toCharArray();
            for(char c : chars) {
                count[c-'a']++;
            }
            StringBuilder sb = new StringBuilder();
            boolean[] visited = new boolean[26];
            for(char c : chars) {
                count[c-'a']--;
                if(visited[c-'a']) {
                    continue;
                }
                while(sb.length() > 0 && c <= sb.charAt(sb.length() - 1) && count[sb.charAt(sb.length() - 1)-'a'] > 0) {
                    visited[sb.charAt(sb.length() - 1)-'a'] = false;
                    sb.deleteCharAt(sb.length() - 1);
                }
                sb.append(c);
                visited[c-'a'] = true;
            }
            return sb.toString();
        }
    }

  • 0
    D

    Hi, by using the visited array, does it mean that you don't need to process the character which has been dealt before?


  • 0
    S

    How is this O(n)


Log in to reply
 

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