Smallest Subsequence of Distinct Characters

Smallest Subsequence of Distinct Characters - Problem

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

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example: For string "bcabc", we need to select one occurrence of each character ('a', 'b', 'c') such that the result is lexicographically smallest while maintaining the original order.

Input & Output

Example 1 — Basic Case

$ Input: s = "bcabc"

› Output: "abc"

💡 Note: We need each distinct character (a,b,c) exactly once. The lexicographically smallest subsequence maintaining original order is "abc"

Example 2 — All Different

$ Input: s = "ecbacba"

› Output: "eacb"

💡 Note: Distinct characters are {a,b,c,e}. The optimal subsequence is "eacb" - we can't improve it while maintaining order

Example 3 — Single Character

$ Input: s = "aaaa"

› Output: "a"

💡 Note: Only one distinct character 'a', so result is just "a"

Constraints

1 ≤ s.length ≤ 1000
s consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

String "bcabc" has distinct characters {a,b,c}

Build Optimal

Use monotonic stack to maintain increasing order

Result

Lexicographically smallest subsequence "abc"

Key Takeaway

🎯 Key Insight: Use monotonic stack to remove larger characters when smaller ones can replace them later

Asked in

G Google 15 a Amazon 12 f Facebook 8

The key insight is using a monotonic stack to maintain lexicographically smallest order while ensuring all distinct characters are included exactly once. Best approach is the monotonic stack solution. Time: O(n), Space: O(k) where k is number of distinct characters.

Common Approaches

Approach	Time	Space	Notes
✓ Monotonic Stack - Optimal Solution	O(n)	O(k)	Use a monotonic stack to build the lexicographically smallest subsequence
Brute Force - Try All Subsequences	O(2^n)	O(2^n)	Generate all possible subsequences and find the lexicographically smallest valid one
Greedy - First Valid Characters	O(n × k)	O(k)	Greedily pick the first occurrence of each character in alphabetical order

Monotonic Stack - Optimal Solution — Algorithm Steps

Count frequency of each character
Use stack to maintain increasing order
Pop larger chars if they appear later
Add current char if not already in result

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Each Char

Scan string left to right, maintaining frequencies

Stack Decision

Pop larger chars if they appear later, add current char

Build Result

Stack contains lexicographically smallest subsequence

Code -

solution.c — C

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

char* solution(char* s) {
    int n = strlen(s);
    int counter[256] = {0};
    
    // Count frequency
    for (int i = 0; i < n; i++) {
        counter[(unsigned char)s[i]]++;
    }
    
    char* stack = malloc((n + 1) * sizeof(char));
    int stackSize = 0;
    bool inStack[256] = {false};
    
    for (int i = 0; i < n; i++) {
        char c = s[i];
        
        // Decrease frequency
        counter[(unsigned char)c]--;
        
        // Skip if already in result
        if (inStack[(unsigned char)c]) {
            continue;
        }
        
        // Pop larger characters that appear later
        while (stackSize > 0 && 
               stack[stackSize - 1] > c && 
               counter[(unsigned char)stack[stackSize - 1]] > 0) {
            char removed = stack[stackSize - 1];
            stackSize--;
            inStack[(unsigned char)removed] = false;
        }
        
        // Add current character
        stack[stackSize++] = c;
        inStack[(unsigned char)c] = true;
    }
    
    stack[stackSize] = '\0';
    return stack;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each character is pushed and popped from stack at most once

✓ Linear Growth

Space Complexity

O(k)

Stack and set store at most k distinct characters

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Monotonic Stack - Optimal Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler