# Easy to understand iterative Java solution

• The basic idea is to find out the smallest result letter by letter (one letter at a time). Here is the thinking process for input "cbacdcbc":

1. find out the last appeared position for each letter;
c - 7
b - 6
a - 2
d - 4
2. find out the smallest index from the map in step 1 (a - 2);
3. the first letter in the final result must be the smallest letter from index 0 to index 2;
4. repeat step 2 to 3 to find out remaining letters.
• the smallest letter from index 0 to index 2: a
• the smallest letter from index 3 to index 4: c
• the smallest letter from index 4 to index 4: d
• the smallest letter from index 5 to index 6: b

so the result is "acdb"

Notes:

• after one letter is determined in step 3, it need to be removed from the "last appeared position map", and the same letter should be ignored in the following steps
• in step 3, the beginning index of the search range should be the index of previous determined letter plus one

``````public class Solution {

public String removeDuplicateLetters(String s) {
if (s == null || s.length() <= 1) return s;

Map<Character, Integer> lastPosMap = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
lastPosMap.put(s.charAt(i), i);
}

char[] result = new char[lastPosMap.size()];
int begin = 0, end = findMinLastPos(lastPosMap);

for (int i = 0; i < result.length; i++) {
char minChar = 'z' + 1;
for (int k = begin; k <= end; k++) {
if (lastPosMap.containsKey(s.charAt(k)) && s.charAt(k) < minChar) {
minChar = s.charAt(k);
begin = k+1;
}
}

result[i] = minChar;
if (i == result.length-1) break;

lastPosMap.remove(minChar);
if (s.charAt(end) == minChar) end = findMinLastPos(lastPosMap);
}

return new String(result);
}

private int findMinLastPos(Map<Character, Integer> lastPosMap) {
if (lastPosMap == null || lastPosMap.isEmpty()) return -1;
int minLastPos = Integer.MAX_VALUE;
for (int lastPos : lastPosMap.values()) {
minLastPos = Math.min(minLastPos, lastPos);
}
return minLastPos;
}

}``````

• Great idea!!!

• It's not easy to understand at all.

• Clever way of thinking!
Wouldn't it be better if you can use an integer array of size 26 instead of Map to store positioning information? Use Arrays.fill(array, -1) to separate the chars that does not appear at all from others.

• Easy to understand and nice explanation.

• easy to understand,thank you very much.

• Nice solution. My 2 cents is this case we know that the string only contains lower case alphabet, so you don't need to use the map.

• great , your solution might not be the fastest, but definitely the easiest to understand (for me at least). Much better than those "concise" solutions without any explanation.

• what is the complexity of this algorithm?

• After comparing my stack solution with others, I found your solution is in another perspective which is very interesting.

``````public class Solution {
public String removeDuplicateLetters(String s) {
char[] array = s.toCharArray();
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < array.length; i++) {
char c = array[i];
map.put(c, i);
}
char[] result = new char[map.size()];
int start = 0;
for (int i = 0; i < result.length; i++) {
int end = findMinPos(map);
char min = 'z' + 1;
for (int j = start; j <= end; j++) {
if (map.containsKey(array[j]) && array[j] < min) {
min = array[j];
start = j + 1;
}
}
result[i] = min;
map.remove(min);
}

return String.valueOf(result);
}

private int findMinPos(HashMap<Character, Integer> map) {
int pos = Integer.MAX_VALUE;
for (Integer end : map.values()) {
pos = Math.min(pos, end);
}
return pos;
}
}
``````

• The worst case complexity is O(nm) with m is the size of the alphabet. Correct me if I am wrong.

• This post is deleted!

• This post is deleted!

• My C++ code, your idea ^_^ ! The idea is really great!

``````class Solution {
public:
typedef pair<int, char>p;
string removeDuplicateLetters(string s) {
string ans;
stack<int>st;
int len = s.length();
vector<int>vis1(26, 0);
vector<int>vis(26, 0);
for(int i = len - 1; i >= 0; --i){
if(vis1[s[i] - 'a']) continue;
vis1[s[i] - 'a'] = 1;
st.push(i);
}
int sta = 0;
while(!st.empty()){
while(!st.empty() && vis[s[st.top()] - 'a']){
st.pop();
continue;
}
if(st.empty()) break;
int ed = st.top();
int pos = -1;
for(int i = sta; i <= ed; ++i){
if(vis[s[i] - 'a']) continue;
if(pos == -1 || s[pos] > s[i] ) pos = i;
}
sta = pos + 1;
if(s[pos] == s[ed]) st.pop();
ans += s[pos];
vis[s[pos] - 'a'] = 1;
}
return ans;
}
};
``````

• This post is deleted!

• @namxh

m is at most 26. So it is O(n) time complexity.

• @WHJ425
Thanks for you sharing your nice solution. At first, I came up with a similar idea with you. But I can figure out how to implement. I rewrite your solution in C++ to make it more concise.

``````class Solution {
int findMinIndex(const unordered_map<char, int>& char_idx) {
int idx = INT_MAX;
for (const auto& pa: char_idx) {
idx = min(idx, pa.second);
}
return idx;
}
public:
string removeDuplicateLetters(string s) {
unordered_map<char, int> char_idx;
// keep the last index of each char
for (int i = 0; i < s.size(); ++i) {
char_idx[s[i]] = i;
}

string res;
int beg = 0;
// if we have char to add
while (!char_idx.empty()) {
int end = findMinIndex(char_idx);
char c = CHAR_MAX;
for (int i = beg; i <= end;  ++i) {
//  find the minimun char in s[beg:end], this char should be in our map
if (s[i] < c && char_idx.find(s[i]) != char_idx.end()) {
c = s[i];
beg = i + 1;
}
}
// erase current char from our map
char_idx.erase(c);
res.push_back(c);
}

return res;
}
};
``````

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