Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is
among all possible results.
Example 1:
Input: s = "bcabc" Output: "abc"
Example 2:
Input: s = "cbacdcbc" Output: "acdb"
Constraints:
1 <= s.length <= 104s consists of lowercase English letters.
Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/
class Solution {
public String removeDuplicateLetters(String s) {
int[] lastIndex = new int[26];
for(int i=0;i<s.length();i++){
char ch = s.charAt(i);
int idx = (int)(ch-'a');
lastIndex[idx]= i ;
}
boolean[] present = new boolean[26];
Stack<Character> st = new Stack<>();
for(int i=0;i<s.length();i++){
char ch = s.charAt(i);
int idx = (int)(ch-'a');
if(present[idx]==false){
while(st.size()>0 && st.peek()>ch && lastIndex[(int)(st.peek()-'a')]>i){
present[(int)(st.peek()-'a')]=false;
st.pop();
}
st.push(ch);
present[idx]=true ;
}
}
StringBuilder sb = new StringBuilder("");
while(st.size()>0){
sb.append(st.pop());
}
return sb.reverse().toString();
}
}
Office:- 660, Sector 14A, Vasundhara, Ghaziabad, Uttar Pradesh - 201012, India
