Java O(n) iterative greedy solution

  • 10

    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) {
            StringBuilder sb = new StringBuilder();
            boolean[] visited = new boolean[26];
            for(char c : chars) {
                if(visited[c-'a']) {
                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);
                visited[c-'a'] = true;
            return sb.toString();

  • 0

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

  • 0

    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.