Code Implementation

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        last_occ = {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 c < stack[-1] and i < last_occ[stack[-1]]:
                seen.remove(stack.pop())
            stack.append(c)
            seen.add(c)
        return ''.join(stack)
      

class Solution {
public:
    string smallestSubsequence(string s) {
        vector<int> last_occ(256, -1);
        for (int i = 0; i < s.length(); ++i)
            last_occ[s[i]] = i;
        vector<bool> seen(256, false);
        string stack = "";
        for (int i = 0; i < s.length(); ++i) {
            char c = s[i];
            if (seen[c]) continue;
            while (!stack.empty() && c < stack.back() && i < last_occ[stack.back()]) {
                seen[stack.back()] = false;
                stack.pop_back();
            }
            stack.push_back(c);
            seen[c] = true;
        }
        return stack;
    }
};
      

class Solution {
    public String smallestSubsequence(String s) {
        int[] last = new int[256];
        for (int i = 0; i < s.length(); ++i)
            last[s.charAt(i)] = i;
        boolean[] seen = new boolean[256];
        StringBuilder stack = new StringBuilder();
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (seen[c]) continue;
            while (stack.length() > 0 && c < stack.charAt(stack.length() - 1) && i < last[stack.charAt(stack.length() - 1)]) {
                seen[stack.charAt(stack.length() - 1)] = false;
                stack.deleteCharAt(stack.length() - 1);
            }
            stack.append(c);
            seen[c] = true;
        }
        return stack.toString();
    }
}
      

var smallestSubsequence = function(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) {
        let c = s[i];
        if (seen.has(c)) continue;
        while (
            stack.length > 0 &&
            c < stack[stack.length - 1] &&
            i < last[stack[stack.length - 1]]
        ) {
            seen.delete(stack.pop());
        }
        stack.push(c);
        seen.add(c);
    }
    return stack.join('');
};
      

Problem Description

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

• The answer must use each unique character in s exactly once (no repeats).
• You are allowed to remove some characters from s, but must keep the original order of the remaining characters.
• There is always exactly one valid solution for each input.

Constraints:
1 <= s.length <= 1000
s consists of lowercase English letters.

Thought Process

At first glance, you might consider generating all subsequences of s that contain each unique character exactly once, and then picking the smallest one in lexicographical order. However, this brute-force approach is infeasible due to the exponential number of possible subsequences.

Instead, we need a way to efficiently build the answer by making local, greedy choices: at each step, decide whether to keep or remove the current character, ensuring that the final subsequence is the smallest possible and contains all unique letters exactly once.

The key insight is that we want the leftmost possible character at each position, but only if we can still include all other required characters later on. So, we need to know if it's safe to remove a character now (because it will appear again later), and we must avoid duplicates.

Solution Approach

To solve this efficiently, we use a monotonic stack and a last occurrence map:

1. Record Last Occurrences: For each character in s, record the last index where it appears. This helps us know if it's safe to remove a character from our current answer, knowing we can add it back later.
2. Use a Stack: Build the answer using a stack. For each character:
   • If it's already in the stack (i.e., in our answer), skip it (since we want each unique character only once).
   • Otherwise, while the top of the stack is lexicographically greater than the current character and the top character will appear again later, pop it from the stack (removing it from the answer for now).
   • Add the current character to the stack and mark it as seen.
3. Build the Result: After processing all characters, the stack contains the smallest subsequence, in order, with each unique character exactly once.

We use a set (or boolean array) to track which characters are currently in the stack for O(1) lookups.

Example Walkthrough

Let's walk through the example s = "cbacdcbc":

1. Last Occurrences: c:7, b:6, a:2, d:5
2. Step-by-step:
   • i=0, c: Stack is empty. Add c.
   • i=1, b: b < c and c appears again at 7, so pop c. Add b.
   • i=2, a: a < b and b appears again at 6, so pop b. Add a.
   • i=3, c: Add c (not in stack).
   • i=4, d: Add d.
   • i=5, c: Skip (already in stack).
   • i=6, b: b not in stack. b < d and d does not appear again, so can't pop d. Add b.
   • i=7, c: Skip (already in stack).

   The stack is [a, c, d, b]. But since we always add to the end, the final answer is acdb.

Time and Space Complexity

• Brute-force: Generating all subsequences is O(2^n) time and space, which is infeasible for even moderate input sizes.
• Optimized Stack Solution:
  • Each character is pushed and popped at most once, so the total time is O(n), where n is the length of s.
  • The space complexity is O(n) for the stack, last occurrence map, and seen set.

Summary

The problem asks us to efficiently find the lexicographically smallest subsequence containing all unique characters from a given string, in order. The stack-based greedy approach, guided by last occurrences and a seen set, allows us to make optimal local decisions that guarantee the global minimum result. This method is both elegant and efficient, running in linear time and space.