Smallest Subsequence of Distinct Characters

medium monotonic stack greedy string

Problem

Given a string s, return the lexicographically smallest subsequence of s that contains all the distinct characters of s exactly once.

Inputs = "bcabc"

Output"abc"

The distinct characters are a, b, c. Among all subsequences using each once ("bca", "bac", "cab", "abc"), "abc" is lexicographically smallest.

s (lowercase letters)

def smallest_subsequence(s):
    last = {c: i for i, c in enumerate(s)}
    stack = []
    seen = set()
    for i, c in enumerate(s):
        if c in seen:
            continue
        while stack and stack[-1] > c and last[stack[-1]] > i:
            seen.discard(stack.pop())
        stack.append(c)
        seen.add(c)
    return "".join(stack)

function smallestSubsequence(s) {
  const last = {};
  for (let i = 0; i < s.length; i++) last[s[i]] = i;
  const stack = [];
  const seen = new Set();
  for (let i = 0; i < s.length; i++) {
    const c = s[i];
    if (seen.has(c)) continue;
    while (stack.length && stack[stack.length - 1] > c && last[stack[stack.length - 1]] > i) {
      seen.delete(stack.pop());
    }
    stack.push(c);
    seen.add(c);
  }
  return stack.join("");
}

class Solution {
    public String smallestSubsequence(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;
        Deque<Character> stack = new ArrayDeque<>();
        boolean[] seen = new boolean[26];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (seen[c - 'a']) continue;
            while (!stack.isEmpty() && stack.peek() > c && last[stack.peek() - 'a'] > i) {
                seen[stack.pop() - 'a'] = false;
            }
            stack.push(c);
            seen[c - 'a'] = true;
        }
        StringBuilder sb = new StringBuilder();
        Iterator<Character> it = stack.descendingIterator();
        while (it.hasNext()) sb.append(it.next());
        return sb.toString();
    }
}

string smallestSubsequence(string s) {
    vector<int> last(26, 0);
    for (int i = 0; i < (int)s.size(); i++) last[s[i] - 'a'] = i;
    string stack;
    vector<bool> seen(26, false);
    for (int i = 0; i < (int)s.size(); i++) {
        char c = s[i];
        if (seen[c - 'a']) continue;
        while (!stack.empty() && stack.back() > c && last[stack.back() - 'a'] > i) {
            seen[stack.back() - 'a'] = false;
            stack.pop_back();
        }
        stack.push_back(c);
        seen[c - 'a'] = true;
    }
    return stack;
}

Explanation

We want the smallest possible string that still uses every distinct letter exactly once. The greedy idea: keep a stack that we try to keep in increasing order, but we can only drop a letter if it will appear again later (otherwise we would lose it forever).

First we record last[c], the last index where each letter appears. We also keep a seen set so we never add the same letter twice. If the current letter is already in the stack, we skip it.

For a new letter c, while the stack top is bigger than c AND that top letter shows up again later (last[top] > i), we pop it. Popping is safe because we will see that letter again, and removing it now lets the smaller c move left.

Example: s = "bcabc". Push b, push c. At a: top c appears later so pop it, top b appears later so pop it, push a. Next b and c are not yet in the stack, so push them. Result is "abc".

Each letter enters and leaves the stack at most once, so the whole thing is a single fast pass.

Time: O(n) Space: O(1) (alphabet bounded)