_316.java

package com.fishercoder.solutions;

import java.util.*;

/**
 * 316. Remove Duplicate Letters
 *
 * Given a string which contains only lowercase letters,
 * remove duplicate letters so that every letter appear once and only once.
 * You must make sure your result is the smallest in lexicographical order among all possible results.

 Example:
 Given "bcabc"
 Return "abc"

 Given "cbacdcbc"
 Return "acdb"
 */
public class _316 {
    /**credit: https://discuss.leetcode.com/topic/32259/java-solution-using-stack-with-comments/2*/
    public String removeDuplicateLetters_use_stack(String s) {
        int[] res = new int[26]; //will contain number of occurences of character (i+'a')
        boolean[] visited = new boolean[26]; //will contain if character (i+'a') is present in current result Stack
        char[] ch = s.toCharArray();
        for(char c: ch){  //count number of occurences of character
            res[c-'a']++;
        }
        Deque<Character> st = new ArrayDeque<>(); // answer stack
        int index;
        for(char c : ch){
            index= c-'a';
            res[index]--;   //decrement number of characters remaining in the string to be analysed
            if(visited[index]) {//if character is already present in stack, dont bother
                continue;
            }
            //if current character is smaller than last character in stack which occurs later in the string again
            //it can be removed and  added later e.g stack = bc remaining string abc then a can pop b and then c
            while(!st.isEmpty() && c<st.peek() && res[st.peek()-'a']!=0){
                visited[st.pop()-'a']=false;
            }
            st.push(c); //add current character and mark it as visited
            visited[index]=true;
        }

        StringBuilder sb = new StringBuilder();
        //pop character from stack and build answer string from back
        while(!st.isEmpty()){
            sb.insert(0,st.pop());
        }
        return sb.toString();
    }

    /**Credit: https://discuss.leetcode.com/topic/31404/a-short-o-n-recursive-greedy-solution*/
    public String removeDuplicateLetters(String s) {
        int[] count = new int[26];
        int pos = 0; // the position for the smallest s[i]
        for (int i = 0; i < s.length(); i++) count[s.charAt(i) - 'a']++;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) < s.charAt(pos)) pos = i;
            count[s.charAt(i) - 'a']--;
            if (count[s.charAt(i) - 'a'] == 0) break;
        }
        return s.length() == 0 ? "" : s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), ""));
    }
}