Scale Engineer

Smallest Subsequence of Distinct Characters

Med
#1027Time: 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).2 companies
Patterns
Greedy
Data structures
StringStackMonotonic Stack
Companies
ByteDanceFactSet

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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).

Walkthrough

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.

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);    }}

Complexity

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).

Trade-offs

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.

Solutions

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);  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem