# Smallest Subsequence of Distinct Characters
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/smallest-subsequence-of-distinct-characters)
Canonical: https://scaleengineer.com/dsa/problems/smallest-subsequence-of-distinct-characters
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String, Stack, Monotonic Stack
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [FactSet](https://scaleengineer.com/companies/factset)
---
## Problem
Given a string `s`, return _the_ _lexicographically smallest_ _subsequence_ _of_ `s` _that contains all the distinct characters of_ `s` _exactly once_.

**Example 1:**

**Input:** s = "bcabc"
**Output:** "abc"

**Example 2:**

**Input:** s = "cbacdcbc"
**Output:** "acdb"

**Constraints:**

* `1 <= s.length <= 1000`
* `s` consists of lowercase English letters.

**Note:** This question is the same as 316: <https://leetcode.com/problems/remove-duplicate-letters/>

# Approaches
## Recursive Greedy Approach
This approach builds the result string one character at a time using recursion. The core idea is to greedily pick the smallest possible character for the current position in the result, while ensuring that the remaining necessary characters can still be found in the rest of the string.
**Time:** O(K * N), where `N` is the length of the string and `K` is the number of unique characters (at most 26). The recursion depth is `K`. In each call, we iterate through a part of the string (O(N)), and `replaceAll()` also takes O(N). · **Space:** O(K * N) in the worst case, due to the recursion stack depth (`K`) and the creation of new substrings at each level (up to `N` characters each).
**Pros:** It's a conceptually clear divide-and-conquer approach.; The greedy choice at each step is easy to understand.
**Cons:** Inefficient due to repeated string scanning and creation of new string objects in each recursive call.; Can lead to a `StackOverflowError` for problems with a larger set of unique characters, although `K` is limited to 26 here.
### Explanation
The function `findSmallest(s)` aims to find the smallest subsequence for a given string `s`. At each step, we must decide which character to pick first. The ideal first character is the smallest one ('a'), but we can only pick it if the remaining unique characters all appear later in the string. We generalize this: we find the smallest character `c` in `s` such that the suffix of `s` after `c` contains all other required unique characters.

To implement this, we can find the last occurrence of every character. Then, we iterate through the string to find the smallest character up to the earliest last-occurrence position. This character is the guaranteed best first character for our subsequence. For example, in `"cbacdcbc"`, the last 'a' is at index 2. We must pick a character from `"cba"`. The smallest is 'a', so we pick 'a'.

Once we've chosen the first character `c` (at index `i`), we append it to our result. Then, we recursively call the function on the rest of the string `s.substring(i+1)`, but we must remove all occurrences of `c` from this substring since we've already used it. The base case for the recursion is when the input string is empty.

```java
class Solution {
    public String smallestSubsequence(String s) {
        if (s.isEmpty()) {
            return "";
        }
        
        // Find the last position of each character
        int[] lastPos = new int[26];
        for (int i = 0; i < s.length(); i++) {
            lastPos[s.charAt(i) - 'a'] = i;
        }
        
        int pos = 0; // Position of the smallest character for the first part of the result
        for (int i = 0; i < s.length(); i++) {
            // Find the lexicographically smallest character
            if (s.charAt(i) < s.charAt(pos)) {
                pos = i;
            }
            // If we are at the last occurrence of a character, we must decide.
            // The smallest character in s[0...i] must be chosen.
            if (i == lastPos[s.charAt(i) - 'a']) {
                break;
            }
        }
        
        char ch = s.charAt(pos);
        // Recursively call on the substring after the chosen character,
        // removing all other occurrences of the chosen character.
        String remainingString = s.substring(pos + 1).replaceAll(String.valueOf(ch), "");
        
        return ch + smallestSubsequence(remainingString);
    }
}
```
### Algorithm
*   Define a recursive function, say `solve(s)`.
*   **Base Case:** If `s` is empty, return an empty string.
*   Find the last occurrence index for each character in `s`.
*   Find the index `pos` of the lexicographically smallest character in `s` up to the point where a character appears for the last time.
    *   Iterate through `s` from left to right. Keep track of the index `pos` of the smallest character seen so far.
    *   If we encounter a character `c` which is the last of its kind in `s` (i.e., its last occurrence index is the current index), we must make a choice from the prefix of `s` we have scanned so far. The best choice is the character at `pos`.
*   Let the chosen character be `ch = s.charAt(pos)`.
*   Form a new string `s_rem` by taking the substring of `s` after `pos` and removing all occurrences of `ch`.
*   Return `ch + solve(s_rem)`.

## Greedy Approach with Stack
This is the most optimal approach. It uses a stack to build the result string and a greedy strategy to ensure it's lexicographically the smallest. We iterate through the input string `s` and decide for each character whether to add it to our result.
**Time:** O(N), where `N` is the length of the string. Although there is a nested `while` loop, each character is pushed onto and popped from the stack at most once. Therefore, the total number of operations is proportional to `N`. · **Space:** O(K), where `K` is the number of unique characters (at most 26). This space is used for the `lastIndex` array, the `seen` array, and the stack. The stack size will not exceed `K`.
**Pros:** Highly efficient with linear time and space complexity.; Single-pass solution (after pre-computation of last indices).
**Cons:** The logic can be slightly less intuitive to grasp initially compared to a direct recursive approach.
### Explanation
The core idea is to maintain a candidate result (using a stack) that is always the lexicographically smallest possible subsequence of the prefix of `s` we have processed so far.

We iterate through the string `s`. For each character `c`:
*   If `c` has already been included in our result stack, we skip it. This ensures each character appears only once.
*   If `c` is not in the stack, we need to add it. Before adding, we check if the character at the top of the stack is greater than the current character `c`. If it is, and if that top character appears again later in the string `s`, we can pop it from the stack. Popping a larger character in favor of a smaller one (`c`) helps in creating a lexicographically smaller result. We repeat this popping process as long as the conditions are met.
*   After the popping phase, we push the current character `c` onto the stack.

To efficiently check if a character appears again later, we can pre-process the string to find the last occurrence index of each character. We also use a boolean array or a set to keep track of the characters currently in the stack for O(1) lookup. After iterating through the entire string, the characters in the stack, when joined together, form the desired smallest subsequence.

```java
import java.util.Stack;

class Solution {
    public String smallestSubsequence(String s) {
        int[] lastIndex = new int[26];
        for (int i = 0; i < s.length(); i++) {
            lastIndex[s.charAt(i) - 'a'] = i;
        }
        
        boolean[] seen = new boolean[26];
        Stack<Character> stack = new Stack<>();
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (seen[c - 'a']) {
                continue;
            }
            
            while (!stack.isEmpty() && c < stack.peek() && i < lastIndex[stack.peek() - 'a']) {
                seen[stack.pop() - 'a'] = false;
            }
            
            stack.push(c);
            seen[c - 'a'] = true;
        }
        
        StringBuilder sb = new StringBuilder();
        for (char c : stack) {
            sb.append(c);
        }
        return sb.toString();
    }
}
```
### Algorithm
*   Create an array `lastIndex` of size 26 to store the last occurrence index of each character in `s`.
*   Initialize an empty stack `stack` to build the result.
*   Initialize a boolean array `seen` of size 26 to keep track of characters already in the stack.
*   Iterate through the input string `s` from left to right with index `i` and character `c`:
    *   If `seen[c - 'a']` is true, continue to the next character.
    *   While the stack is not empty, the character at the top of the stack is lexicographically greater than `c`, AND the last occurrence of the top character is after the current index `i`:
        *   Pop the character from the stack.
        *   Mark the popped character as not seen (e.g., `seen[popped_char - 'a'] = false`).
    *   Push the current character `c` onto the stack.
    *   Mark `c` as seen (e.g., `seen[c - 'a'] = true`).
*   After the loop, build a string from the characters in the stack. This string is the result.

# Solutions
### Java

```java
class Solution {
public
  String smallestSubsequence(String text) {
    int[] cnt = new int[26];
    for (char c : text.toCharArray()) {
      ++cnt[c - 'a'];
    }
    boolean[] vis = new boolean[26];
    char[] cs = new char[text.length()];
    int top = -1;
    for (char c : text.toCharArray()) {
      --cnt[c - 'a'];
      if (!vis[c - 'a']) {
        while (top >= 0 && c < cs[top] && cnt[cs[top] - 'a'] > 0) {
          vis[cs[top--] - 'a'] = false;
        }
        cs[++top] = c;
        vis[c - 'a'] = true;
      }
    }
    return String.valueOf(cs, 0, top + 1);
  }
}

```

### CPP

```cpp
class Solution {
public:
  string smallestSubsequence(string s) {
    int n = s.size();
    int last[26] = {0};
    for (int i = 0; i < n; ++i) {
      last[s[i] - 'a'] = i;
    }
    string ans;
    int mask = 0;
    for (int i = 0; i < n; ++i) {
      char c = s[i];
      if ((mask >> (c - 'a')) & 1) {
        continue;
      }
      while (!ans.empty() && ans.back() > c && last[ans.back() - 'a'] > i) {
        mask ^= 1 << (ans.back() - 'a');
        ans.pop_back();
      }
      ans.push_back(c);
      mask |= 1 << (c - 'a');
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def smallestSubsequence(self, s: str) -> str: last = {c: i for i, c in enumerate(s)} stk = [] vis = set() for i, c in enumerate(s): if c in vis: continue while stk and stk[- 1] > c and last[stk[- 1]] > i: vis . remove(stk . pop()) stk . append(c) vis . add(c) return "" . join(stk)

```