Smallest Subsequence of Distinct Characters - Solution

Q: Is Smallest Subsequence of Distinct Characters easy or hard?

The problem is classified as Medium difficulty on most coding platforms. The challenge is recognizing the greedy condition for removing characters and implementing it using a monotonic stack. Once the pattern is known, the implementation is straightforward and runs in linear time.

Q: Smallest Subsequence of Distinct Characters Python/Java solution

Both Python and Java implementations follow the same logic: maintain a stack, track remaining character counts, and record whether a character is already in the result. During iteration, pop larger characters that still appear later and push the current character if it has not been used. This results in an O(n) time solution suitable for large inputs.

Q: How to solve Smallest Subsequence of Distinct Characters in O(n)?

Scan the string while maintaining a stack for the current subsequence and a frequency count of remaining characters. If the current character is smaller than the stack top and the top character appears later again, pop it from the stack. Add the current character only if it is not already included. This greedy stack process ensures each character appears once and produces the lexicographically smallest result in O(n) time.

Q: What is the best approach for Smallest Subsequence of Distinct Characters?

The monotonic stack approach is the most efficient and commonly expected solution. It processes the string once while maintaining a stack that keeps characters in lexicographically increasing order. By removing larger characters that appear later, it guarantees the smallest valid subsequence. The time complexity is O(n) with constant auxiliary space for the alphabet.

Q: Is Smallest Subsequence of Distinct Characters asked at Google/Amazon/Meta?

This pattern appears frequently in interviews at large tech companies because it tests greedy reasoning and stack usage. Variants of the problem have been reported in interviews at companies like Amazon and Google, often under topics such as monotonic stack or lexicographically smallest sequence problems.

Q: What data structure is used in Smallest Subsequence of Distinct Characters?

A stack is the core data structure. It stores the characters of the current candidate subsequence while allowing efficient removal of larger characters that appear earlier. Additional arrays or hash sets track character frequencies and whether a character is already present in the stack.

Q: What is the time complexity of Smallest Subsequence of Distinct Characters?

The optimal solution runs in O(n) time where n is the length of the string. Each character is pushed to and popped from the stack at most once. Frequency counting and membership checks are constant time, giving linear complexity overall with O(1) extra space for lowercase characters.

The 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/

Approach overview

Problem Overview: Given a string s, return the lexicographically smallest subsequence that contains every distinct character exactly once. You can delete characters but must preserve relative order. The challenge is choosing which occurrences to keep so the final sequence is both unique and minimal in lexicographic order.

Approach 1: Brute Force with Subsequence Checking (Exponential Time)

The naive idea is to generate subsequences of the string and filter those that contain all unique characters exactly once. Among valid candidates, select the lexicographically smallest. This approach quickly becomes impractical because a string of length n has 2^n subsequences. Even with pruning using sets to track distinct characters, the worst‑case time complexity remains O(2^n) with O(n) auxiliary space. This method mainly helps understand the problem constraints before optimizing.

Approach 2: Monotonic Stack (O(n) time, O(1) space)

The optimal approach uses a stack to maintain the current best subsequence while scanning the string once. First count how many times each character appears. While iterating through the string, push characters onto the stack only if they are not already included. Before pushing, compare the current character with the top of the stack. If the stack top is lexicographically larger and appears again later in the string, you can safely pop it to build a smaller result. This creates a monotonic stack that keeps the subsequence lexicographically minimal. A boolean array tracks whether a character is already used. The algorithm runs in O(n) time since each character is pushed and popped at most once, and uses O(1) space for the fixed alphabet.

Approach 3: Greedy with Frequency Counting (O(n) time, O(1) space)

This method expresses the same idea in a greedy framework. Track remaining character frequencies and maintain a result structure similar to a stack. When processing a new character, decrement its remaining count. If the character already exists in the result, skip it. Otherwise, repeatedly remove the last character if it is larger than the current one and still appears later. This greedy rule guarantees the smallest possible prefix while ensuring all characters remain available. The implementation relies on constant‑time membership checks and frequency arrays, making it efficient for large strings. It naturally combines ideas from greedy algorithms and stack processing.

Recommended for interviews: The monotonic stack solution is what interviewers expect. It demonstrates control over greedy reasoning, stack operations, and frequency tracking. Mentioning the brute force idea shows understanding of the search space, but implementing the O(n) stack-based approach proves you can optimize string problems effectively.

Approach 1: Stack-based Approach

This approach utilizes a stack to build the smallest lexicographical subsequence. We ensure that each character appears only once by popping the top of the stack if it's greater than the current character and can appear later in the string.

Python

def smallest_subsequence(s: str) -> str:
    last_index = {c: i for i, c in enumerate(s)}
    stack = []
    in_stack = set()
    for i, c in enumerate(s):
        if c in in_stack:
            continue
        while stack and stack[-1] > c and last_index[stack[-1]] > i:
            in_stack.remove(stack.pop())
        stack.append(c)
        in_stack.add(c)
    return ''.join(stack)

# Example Usage
print(smallest_subsequence("bcabc"))  # Output: "abc"
print(smallest_subsequence("cbacdcbc"))  # Output: "acdb"

Java

import java.util.*;

public class SmallestSubsequence {
    public static String smallestSubsequence(String s) {
        int[] lastIndex = new int[256];
        boolean[] inStack = new boolean[256];
        for (int i = 0; i < s.length(); i++) {
            lastIndex[s.charAt(i)] = i;
        }
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (inStack[ch]) continue;
            while (!stack.isEmpty() && stack.peek() > ch && lastIndex[stack.peek()] > i) {
                inStack[stack.pop()] = false;
            }
            stack.push(ch);
            inStack[ch] = true;
        }
        StringBuilder sb = new StringBuilder();
        for (char ch : stack) {
            sb.append(ch);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(smallestSubsequence("bcabc")); // Output: "abc"
        System.out.println(smallestSubsequence("cbacdcbc")); // Output: "acdb"
    }
}

C++

#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;

string smallestSubsequence(string s) {
    int n = s.size();
    vector<int> lastIndex(256, 0);
    vector<bool> inStack(256, false);
    for (int i = 0; i < n; i++) {
        lastIndex[s[i]] = i;
    }
    stack<char> stk;
    for (int i = 0; i < n; i++) {
        if (inStack[s[i]]) continue;
        while (!stk.empty() && stk.top() > s[i] && lastIndex[stk.top()] > i) {
            inStack[stk.top()] = false;
            stk.pop();
        }
        stk.push(s[i]);
        inStack[s[i]] = true;
    }
    string result;
    while (!stk.empty()) {
        result += stk.top();
        stk.pop();
    }
    reverse(result.begin(), result.end());
    return result;
}

int main() {
    cout << smallestSubsequence("bcabc") << endl; // Output: "abc"
    cout << smallestSubsequence("cbacdcbc") << endl; // Output: "acdb"
    return 0;
}

JavaScript

function smallestSubsequence(s) {
    const lastIndex = Array(256).fill(0);
    const inStack = Array(256).fill(false);
    const stack = [];

    for (let i = 0; i < s.length; i++) {
        lastIndex[s.charCodeAt(i)] = i;
    }

    for (let i = 0; i < s.length; i++) {
        const charCode = s.charCodeAt(i);
        if (inStack[charCode]) continue;
        while (stack.length > 0 && stack[stack.length - 1] > s[i] && lastIndex[stack[stack.length - 1].charCodeAt()] > i) {
            inStack[stack.pop().charCodeAt()] = false;
        }
        stack.push(s[i]);
        inStack[charCode] = true;
    }

    return stack.join('');
}

console.log(smallestSubsequence("bcabc")); // Output: "abc"
console.log(smallestSubsequence("cbacdcbc")); // Output: "acdb"

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

char* smallestSubsequence(char* s) {
    int n = strlen(s);
    bool inStack[256] = {false};
    int lastIndex[256];
    for (int i = 0; i < n; i++) {
        lastIndex[s[i]] = i;
    }
    char stack[n + 1];
    int stackIndex = -1;
    for (int i = 0; i < n; i++) {
        if (inStack[s[i]]) continue;
        while (stackIndex >= 0 && stack[stackIndex] > s[i] && lastIndex[stack[stackIndex]] > i) {
            inStack[stack[stackIndex]] = false;
            stackIndex--;
        }
        stack[++stackIndex] = s[i];
        inStack[s[i]] = true;
    }
    stack[++stackIndex] = '\0';
    return strdup(stack); // Duplicate stack to return as a new string
}

int main() {
    printf("%s\n", smallestSubsequence("bcabc")); // Output: "abc"
    printf("%s\n", smallestSubsequence("cbacdcbc")); // Output: "acdb"
    return 0;
}

using System;
using System.Collections.Generic;

public class SmallestSubsequence {
    public static string SmallestSubsequence(string s) {
        int[] lastIndex = new int[256];
        bool[] inStack = new bool[256];
        for (int i = 0; i < s.Length; i++) {
            lastIndex[s[i]] = i;
        }
        Stack<char> stack = new Stack<char>();
        for (int i = 0; i < s.Length; i++) {
            char ch = s[i];
            if (inStack[ch]) continue;
            while (stack.Count > 0 && stack.Peek() > ch && lastIndex[stack.Peek()] > i) {
                inStack[stack.Pop()] = false;
            }
            stack.Push(ch);
            inStack[ch] = true;
        }
        char[] result = stack.ToArray();
 Array.Reverse(result);
        return new string(result);
    }

    public static void Main() {
        Console.WriteLine(SmallestSubsequence("bcabc")); // Output: "abc"
        Console.WriteLine(SmallestSubsequence("cbacdcbc")); // Output: "acdb"
    }
}

The function uses a dictionary to store the last position of each character. The stack is used to build the result string, and a set in_stack is used to keep track of the characters already in the stack.

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1) (excluding the result), due to constant alphabet size.

Try this approach in the editor

Approach 2: Greedy Algorithm with Counting

This approach involves using a count of characters while greedily constructing the result by iteratively checking character positions and ensuring minimal lexicographical ordering.

Python

def smallest_subsequence(s: str) -> str:
    count = {c: s.count(c) for c in set(s)}
    result = []
    in_result = set()

    for c in s:
        count[c] -= 1
        if c in in_result: 
            continue
        while result and result[-1] > c and count[result[-1]] > 0:
            in_result.remove(result.pop())
        result.append(c)
        in_result.add(c)

    return ''.join(result)

# Example Usage
print(smallest_subsequence("bcabc"))  # Output: "abc"
print(smallest_subsequence("cbacdcbc"))  # Output: "acdb"

Java

import java.util.*;

public class SmallestSubsequence {
    public static String smallestSubsequence(String s) {
        int[] count = new int[256];
        boolean[] taken = new boolean[256];
        for (char c : s.toCharArray()) {
            count[c]++;
        }
        StringBuilder result = new StringBuilder();
        for (char c : s.toCharArray()) {
            count[c]--;
            if (taken[c]) continue;
            while (result.length() > 0 && result.charAt(result.length() - 1) > c && count[result.charAt(result.length() - 1)] > 0) {
                taken[result.charAt(result.length() - 1)] = false;
                result.deleteCharAt(result.length() - 1);
            }
            result.append(c);
            taken[c] = true;
        }
        return result.toString();
    }

    public static void main(String[] args) {
        System.out.println(smallestSubsequence("bcabc")); // Output: "abc"
        System.out.println(smallestSubsequence("cbacdcbc")); // Output: "acdb"
    }
}

C++

#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;

string smallestSubsequence(string s) {
    vector<int> count(256, 0);
    vector<bool> taken(256, false);
    string result;
    for (char c : s) {
        count[c]++;
    }
    for (char c : s) {
        count[c]--;
        if (taken[c]) continue;
        while (!result.empty() && result.back() > c && count[result.back()] > 0) {
            taken[result.back()] = false;
            result.pop_back();
        }
        result.push_back(c);
        taken[c] = true;
    }
    return result;
}

int main() {
    cout << smallestSubsequence("bcabc") << endl; // Output: "abc"
    cout << smallestSubsequence("cbacdcbc") << endl; // Output: "acdb"
    return 0;
}

JavaScript

function smallestSubsequence(s) {
    const count = {};
    const result = [];
    const inResult = new Set();

    for (let char of s) {
        count[char] = (count[char] || 0) + 1;
    }

    for (let char of s) {
        count[char]--;
        if (inResult.has(char)) continue;
        while (result.length > 0 && result[result.length - 1] > char && count[result[result.length - 1]] > 0) {
            inResult.delete(result.pop());
        }
        result.push(char);
        inResult.add(char);
    }

    return result.join('');
}

console.log(smallestSubsequence("bcabc")); // Output: "abc"
console.log(smallestSubsequence("cbacdcbc")); // Output: "acdb"

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

char* smallestSubsequence(char* s) {
    int count[256] = {0};
    int n = strlen(s);
    char result[n+1];
    bool taken[256] = {false};
    for (int i = 0; i < n; i++) {
        count[s[i]]++;
    }
    int index = 0;
    for (int i = 0; i < n; i++) {
        count[s[i]]--;
        if (taken[s[i]]) continue;
        while (index > 0 && result[index - 1] > s[i] && count[result[index - 1]] > 0) {
            taken[result[index - 1]] = false;
            index--;
        }
        result[index++] = s[i];
        taken[s[i]] = true;
    }
    result[index] = '\0';
    return strdup(result); // Return a new string
}

int main() {
    printf("%s\n", smallestSubsequence("bcabc")); // Output: "abc"
    printf("%s\n", smallestSubsequence("cbacdcbc")); // Output: "acdb"
    return 0;
}

using System;
using System.Collections.Generic;

public class SmallestSubsequence {
    public static string SmallestSubsequence(string s) {
        int[] count = new int[256];
        bool[] taken = new bool[256];
        char[] result = new char[s.Length];
        foreach (char c in s) {
            count[c]++;
        }
        int index = 0;
        foreach (char c in s) {
            count[c]--;
            if (taken[c]) continue;
            while (index > 0 && result[index - 1] > c && count[result[index - 1]] > 0) {
                taken[result[--index]] = false;
            }
            result[index++] = c;
            taken[c] = true;
        }
        return new string(result, 0, index);
    }

    public static void Main() {
        Console.WriteLine(SmallestSubsequence("bcabc")); // Output: "abc"
        Console.WriteLine(SmallestSubsequence("cbacdcbc")); // Output: "acdb"
    }
}

The Python solution uses a dictionary for character counts and a list combined with a set to build the output string in optimal order.

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), because alphabet size is constant.

Try this approach in the editor

Approach 3: Default Approach

TypeScript

function smallestSubsequence(s: string): string {
    const f = (c: string): number => c.charCodeAt(0) - 'a'.charCodeAt(0);
    const last: number[] = new Array(26).fill(0);
    for (const [i, c] of [...s].entries()) {
        last[f(c)] = i;
    }
    const stk: string[] = [];
    let mask = 0;
    for (const [i, c] of [...s].entries()) {
        const x = f(c);
        if ((mask >> x) & 1) {
            continue;
        }
        while (stk.length && stk[stk.length - 1] > c && last[f(stk[stk.length - 1])] > i) {
            mask ^= 1 << f(stk.pop()!);
        }
        stk.push(c);
        mask |= 1 << x;
    }
    return stk.join('');
}

func smallestSubsequence(s string) string {
	last := make([]int, 26)
	for i, c := range s {
		last[c-'a'] = i
	}
	stk := []rune{}
	vis := make([]bool, 128)
	for i, c := range s {
		if vis[c] {
			continue
		}
		for len(stk) > 0 && stk[len(stk)-1] > c && last[stk[len(stk)-1]-'a'] > i {
			vis[stk[len(stk)-1]] = false
			stk = stk[:len(stk)-1]
		}
		stk = append(stk, c)
		vis[c] = true
	}
	return string(stk)
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Stack-based Approach	Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1) (excluding the result), due to constant alphabet size.
Greedy Algorithm with Counting	Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), because alphabet size is constant.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Subsequence Enumeration	O(2^n)	O(n)	Conceptual understanding or very small inputs
Monotonic Stack	O(n)	O(1)	Best general solution for interviews and production
Greedy with Frequency Counting	O(n)	O(1)	Alternative implementation using greedy reasoning

Frequently asked questions

Is Smallest Subsequence of Distinct Characters easy or hard?

The problem is classified as Medium difficulty on most coding platforms. The challenge is recognizing the greedy condition for removing characters and implementing it using a monotonic stack. Once the pattern is known, the implementation is straightforward and runs in linear time.

Smallest Subsequence of Distinct Characters Python/Java solution

Both Python and Java implementations follow the same logic: maintain a stack, track remaining character counts, and record whether a character is already in the result. During iteration, pop larger characters that still appear later and push the current character if it has not been used. This results in an O(n) time solution suitable for large inputs.

How to solve Smallest Subsequence of Distinct Characters in O(n)?

Scan the string while maintaining a stack for the current subsequence and a frequency count of remaining characters. If the current character is smaller than the stack top and the top character appears later again, pop it from the stack. Add the current character only if it is not already included. This greedy stack process ensures each character appears once and produces the lexicographically smallest result in O(n) time.

What is the best approach for Smallest Subsequence of Distinct Characters?

The monotonic stack approach is the most efficient and commonly expected solution. It processes the string once while maintaining a stack that keeps characters in lexicographically increasing order. By removing larger characters that appear later, it guarantees the smallest valid subsequence. The time complexity is O(n) with constant auxiliary space for the alphabet.

Is Smallest Subsequence of Distinct Characters asked at Google/Amazon/Meta?

This pattern appears frequently in interviews at large tech companies because it tests greedy reasoning and stack usage. Variants of the problem have been reported in interviews at companies like Amazon and Google, often under topics such as monotonic stack or lexicographically smallest sequence problems.

What data structure is used in Smallest Subsequence of Distinct Characters?

A stack is the core data structure. It stores the characters of the current candidate subsequence while allowing efficient removal of larger characters that appear earlier. Additional arrays or hash sets track character frequencies and whether a character is already present in the stack.

What is the time complexity of Smallest Subsequence of Distinct Characters?

The optimal solution runs in O(n) time where n is the length of the string. Each character is pushed to and popped from the stack at most once. Frequency counting and membership checks are constant time, giving linear complexity overall with O(1) extra space for lowercase characters.

Smallest Subsequence of Distinct Characters solution and explanation

The problem

Approach overview

Approach 1: Stack-based Approach

Approach 2: Greedy Algorithm with Counting

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Smallest Subsequence of Distinct Characters solution and explanation

The problem

Approach overview

Approach 1: Stack-based Approach

Approach 2: Greedy Algorithm with Counting

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems