Remove Duplicate Letters - Practice Coding Problems

Remove Duplicate Letters - Problem

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Lexicographical order means dictionary order - for example, "abc" comes before "acb" because 'b' < 'c' at the first differing position.

The key challenge is not just removing duplicates, but doing so while maintaining the lexicographically smallest possible result.

Input & Output

Example 1 — Basic Case

$ Input: s = "bcabc"

› Output: "abc"

💡 Note: We need one occurrence of each letter: a, b, c. The lexicographically smallest arrangement is "abc". We can remove the duplicate 'b' at index 3 and duplicate 'c' at index 4.

Example 2 — Different Order

$ Input: s = "cbacdcbc"

› Output: "acdb"

💡 Note: Unique letters are: a, b, c, d. The lexicographically smallest string containing all of them exactly once is "acdb". Note that "abcd" is not possible given the character positions in the original string.

Example 3 — Already Optimal

$ Input: s = "abc"

› Output: "abc"

💡 Note: All characters are unique and already in lexicographically smallest order, so no changes needed.

Constraints

1 ≤ s.length ≤ 10⁴
s consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

String "bcabc" has duplicates: b(2), c(2), a(1)

Smart Removal

Use monotonic stack to decide which duplicates to remove

Optimal Output

Result "abc" is lexicographically smallest with all unique letters

Key Takeaway

🎯 Key Insight: Use a monotonic stack to greedily build the lexicographically smallest result by removing larger characters when we know they can be added back later

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is to use a greedy approach with a monotonic stack. We can remove a character from our current result if: (1) it's larger than the current character, and (2) it appears again later in the string. This ensures we build the lexicographically smallest string. Best approach is Monotonic Stack: Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Subsequences	O(2ⁿ × n)	O(2ⁿ × n)	Generate all possible subsequences with unique characters and find the lexicographically smallest
Greedy with Monotonic Stack	O(n)	O(1)	Use a monotonic stack to build the lexicographically smallest result by removing characters when beneficial

Brute Force - Generate All Subsequences — Algorithm Steps

Generate all possible subsequences
Filter those with exactly one occurrence of each character
Sort lexicographically and return the smallest

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate All

Create all possible subsequences using bit masking

Validate

Check each subsequence has all unique chars exactly once

Compare

Find lexicographically smallest valid subsequence

Code -

solution.c — C

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

char* solution(char* s) {
    int n = strlen(s);
    int chars[26] = {0};
    
    // Count unique characters
    for (int i = 0; i < n; i++) {
        chars[s[i] - 'a'] = 1;
    }
    int uniqueCount = 0;
    for (int i = 0; i < 26; i++) {
        if (chars[i]) uniqueCount++;
    }
    
    char* minResult = malloc(n + 1);
    strcpy(minResult, s);
    int found = 0;
    
    // Generate all possible subsequences
    for (int mask = 1; mask < (1 << n); mask++) {
        char subseq[n + 1];
        int pos = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                subseq[pos++] = s[i];
            }
        }
        subseq[pos] = '\0';
        
        // Check if all unique chars are present exactly once
        int subseqChars[26] = {0};
        for (int i = 0; i < pos; i++) {
            subseqChars[subseq[i] - 'a']++;
        }
        
        int valid = 1;
        int subseqUniqueCount = 0;
        for (int i = 0; i < 26; i++) {
            if (chars[i] && subseqChars[i] != 1) {
                valid = 0;
                break;
            }
            if (subseqChars[i] > 0) subseqUniqueCount++;
        }
        
        if (valid && subseqUniqueCount == uniqueCount && pos == uniqueCount) {
            if (!found || strcmp(subseq, minResult) < 0) {
                strcpy(minResult, subseq);
                found = 1;
            }
        }
    }
    
    return minResult;
}

int main() {
    char s[1000];
    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(2ⁿ × n)

Generate 2^n subsequences, each taking O(n) time to validate and compare

✓ Linear Growth

Space Complexity

O(2ⁿ × n)

Store all possible subsequences, each of length up to n

⚡ Linearithmic Space

85.0K Views

Medium Frequency

~25 min Avg. Time

2.4K 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

Brute Force - Generate All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler