RemoveLetters { public String removeDuplicateLetters(String s) { int[] cnum = new int[26]; for (char c : s.toCharArray()) { cnum[c - 'a']++; } boolean[] visited = new boolean[26]; Deque<Character> deque = new LinkedList<>(); for (char c : s.toCharArray()) { int index = c - 'a'; cnum[index]--; if (visited[index]) { continue; } while(!deque.isEmpty() && deque.getLast() > c && cnum[deque.getLast() - 'a'] > 0) { visited[deque.removeLast() - 'a'] = false; } deque.addLast(c); visited[index] = true; } StringBuilder sb = new StringBuilder(); while(!deque.isEmpty()) { sb.append(deque.removeFirst()); } return sb.toString(); }  String removeDuplicateLetters(String s);  }
@Test(dataProvider = "strings") public void testRemoveDuplicateLetters(String original, String removed) { assertEquals(removed, new RemoveLetters().removeDuplicateLetters(original)); }