Remove Duplicate Letters

Published at23 Jul 2026

Stack Hard 0 views

Like0

Given a string of lowercase letters, remove duplicate letters so each appears exactly once. The result must be the smallest lexicographical result possible while preserving the relative order of first occurrences of each letter.

A monotonic increasing stack with a frequency counter solves this. Count frequencies. Iterate, decrement count for each char. If already used, skip. While the stack top is greater than the current char and the top char appears later, pop the top (mark as unused). Push current char, mark as used. This greedy approach ensures the smallest lexicographical result.

Example Input & Output

Example 1

Input

abcd

Output

abcd

Explanation

No duplicates.

Example 2

Input

bcabc

Output

abc

Explanation

Smallest lexicographical.

Example 3

Input

cbacdcbc

Output

acdb

Explanation

Lexicographically smallest.

Algorithm Flow

Recommendation Algorithm Flow for Remove Duplicate Letters

Solution Approach

Remove duplicate letters from a string to produce the smallest lexicographic result. Use a monotonic stack with a frequency counter and a boolean array tracking used characters. Count character frequencies first. Iterate through each character, decrement its count. If it is already in the result (used), skip it. While the stack is not empty and the current character is smaller than the top of the stack and the top character still appears later, pop the stack and mark it unused. Push the current character.

function removeDuplicateLetters(s) {
  var count = {}, used = {}, stack = [];
  for (var i = 0; i < s.length; i++) count[s[i]] = (count[s[i]] || 0) + 1;
  for (var i = 0; i < s.length; i++) {
    count[s[i]]--;
    if (used[s[i]]) continue;
    while (stack.length && s[i] < stack[stack.length - 1] && count[stack[stack.length - 1]] > 0) {
      used[stack.pop()] = false;
    }
    stack.push(s[i]);
    used[s[i]] = true;
  }
  return stack.join('');
}

The stack maintains the result in lexicographic order. A character is popped if a smaller character appears later and the current one is no longer needed. Each character is processed once.

Time complexity is O(n), space complexity is O(k).

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;
class Solution {
    public String solution(String s) {
        int[] cnt = new int[26];
        boolean[] used = new boolean[26];
        Stack<Character> stack = new Stack<>();
        for (char ch : s.toCharArray()) cnt[ch - 'a']++;
        for (char ch : s.toCharArray()) {
            cnt[ch - 'a']--;
            if (used[ch - 'a']) continue;
            while (!stack.isEmpty() && ch < stack.peek() && cnt[stack.peek() - 'a'] > 0)
                used[stack.pop() - 'a'] = false;
            stack.push(ch);
            used[ch - 'a'] = true;
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) sb.insert(0, stack.pop());
        return sb.toString();
    }
}

javascript

function solution(s) {
  var cnt = {}, stack = [], used = {};
  for (var i = 0; i < s.length; i++) cnt[s[i]] = (cnt[s[i]]||0) + 1;
  for (var i = 0; i < s.length; i++) {
    var ch = s[i];
    cnt[ch]--;
    if (used[ch]) continue;
    while (stack.length && ch < stack[stack.length-1] && cnt[stack[stack.length-1]] > 0)
      used[stack.pop()] = false;
    stack.push(ch);
    used[ch] = true;
  }
  return stack.join('');
}

php

<?php
function solution($s) {
    $cnt = array_count_values(str_split($s));
    $stack = []; $used = [];
    for ($i = 0; $i < strlen($s); $i++) {
        $ch = $s[$i];
        $cnt[$ch]--;
        if (!empty($used[$ch])) continue;
        while (!empty($stack) && $ch < end($stack) && $cnt[end($stack)] > 0)
            $used[array_pop($stack)] = false;
        array_push($stack, $ch);
        $used[$ch] = true;
    }
    return implode('', $stack);
}

python

def solution(s):
    from collections import Counter
    count = Counter(s)
    stack = []
    used = set()
    for ch in s:
        count[ch] -= 1
        if ch in used:
            continue
        while stack and ch < stack[-1] and count[stack[-1]] > 0:
            used.remove(stack.pop())
        stack.append(ch)
        used.add(ch)
    return ''.join(stack)

rust

fn solution(s: &str) -> String {
    let mut cnt = [0; 26];
    for ch in s.chars() { cnt[(ch as usize) - 97] += 1; }
    let mut stack: Vec<char> = Vec::new();
    let mut used = [false; 26];
    for ch in s.chars() {
        let idx = (ch as usize) - 97;
        cnt[idx] -= 1;
        if used[idx] { continue; }
        while let Some(&top) = stack.last() {
            let tidx = (top as usize) - 97;
            if ch >= top || cnt[tidx] == 0 { break; }
            used[tidx] = false;
            stack.pop();
        }
        stack.push(ch);
        used[idx] = true;
    }
    stack.iter().collect()
}

typescript

function solution(s: string): string {
    var cnt: any = {}, stack: string[] = [], used: any = {};
    for (var i = 0; i < s.length; i++) cnt[s[i]] = (cnt[s[i]]||0) + 1;
    for (var i = 0; i < s.length; i++) {
        var ch = s[i];
        cnt[ch]--;
        if (used[ch]) continue;
        while (stack.length && ch < stack[stack.length-1] && cnt[stack[stack.length-1]] > 0)
            used[stack.pop() as string] = false;
        stack.push(ch);
        used[ch] = true;
    }
    return stack.join('');
}

Related Stack Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Remove Duplicate Letters

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Stack Challenges

Maximum Nesting Depth

Simplify Path

Final Prices With Discount

Clear Digits

Crawler Log Folder

Build Array With Stack Operations

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.