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

Count frequencies. Iterate, decrement. Skip if used. While stack top > char and top appears later, pop. Push char.

function solution(s) {
  var cnt = {};
  for (var i = 0; i < s.length; i++) cnt[s[i]] = (cnt[s[i]]||0) + 1;
  var stack = [], used = {};
  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("");
}

Time O(n), Space O(n).

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.