LeetCode Q 1081 - Smallest Subsequence of Distinct Characters

Return the lexicographically smallest subsequence of text that contains all the distinct characters of text exactly once.

Example 1: Input: "cdadabcc" ; Output: "adbc"
Example 2: Input: "abcd" ; Output: "abcd"
Example 3: Input: "ecbacba" ; Output: "eacb"
Example 4: Input: "leetcode" ; Output: "letcod"

Note:

1 <= text.length <= 1000
text consists of lowercase English letters.

Solution:

The key point is we are trying to greedily build a monotonically increasing result string. If the next character is smaller than the back of the result string, we remove larger characters from the back providing there are more occurrences of that character later in the input string.

Code:

public String smallestSubsequence(String text) {
  Deque<Character> stack = new ArrayDeque<>();

  int[] count = new int[26];
  boolean[] seen = new boolean[26];
  for (char ch: text.toCharArray()) count[ch - 'a']++;

  for (char ch: text.toCharArray()) {
    if (seen[ch - 'a']) continue;
    while (!stack.isEmpty() && stack.peek() > ch && count[stack.peek() - 'a'] > 0) 
      seen[stack.pop() - 'a'] = false;

    stack.push(ch);
    count[ch - 'a']--;
    seen[ch - 'a'] = true;
  } 

  StringBuilder sb = new StringBuilder(); 
  while (!stack.isEmpty()) sb.append(stack.pop());

  return sb.reverse().toString();
}

Reprint policy