Problem 1081

Abstract / Summary

Given a string, find the smallest ordered sequence of its unique letters that keeps them in their first appearance order.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1081.py

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        result = ""

        # count chars
        freq = defaultdict(int)
        for c in s:
            freq[c] += 1

        need = set(s)
        for c in s:
            # adjust counter
            freq[c] -= 1
            if c not in need:
                continue

            # check last char: if it's (lexicographically) larger and will appear again in s
            # then replace it by the current character
            while result and result[-1] > c and freq[result[-1]] > 0:
                need.add(result[-1])
                result = result[: -1]

            result += c
            need.discard(c)

        return result
26 lines | 734 bytes | submitted February 29, 2024 | GitHub   23% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 61% (100k+ submissions).

Typical patterns to solve this problem:
  • Greedy
  • Monotonic Stack
  • Stack
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation computes the lexicographically smallest subsequence of a given string that contains each distinct character exactly once. It proceeds in a single left-to-right pass, maintaining a mutable result string, a frequency map of remaining characters, and a set of characters that still need to be placed in the result. By adjusting the result on the fly, the algorithm guarantees that the final string respects both the uniqueness and ordering constraints.

Core Logic

The algorithm begins by counting how many times each character appears in the input. This frequency map is stored in a defaultdict(int), allowing constant-time increments as the string is scanned.

freq = defaultdict(int)
for c in s:
    freq[c] += 1

A set named need is initialized with all unique characters from the input. This set tracks which characters have not yet been added to the result.

need = set(s)

The main loop iterates over each character c in the original string. For each iteration the frequency of c is decremented, reflecting that one occurrence has been processed.

for c in s:
    freq[c] -= 1
    if c not in need:
        continue

If the current character is already satisfied (i.e., not in need), the loop skips further processing, ensuring that each character contributes at most once to the final subsequence.

Maintaining Lexicographic Minimality

When a needed character is encountered, the algorithm checks whether the last character in the current result is larger than c and will appear again later in the string (indicated by a positive remaining frequency). If both conditions hold, the larger character can safely be removed, because a smaller character (c) can take its place while still allowing the removed character to be re-added later. This removal is performed inside a while loop that repeatedly pops the last character until the condition no longer holds.

while result and result[-1] > c and freq[result[-1]] > 0:
    need.add(result[-1])
    result = result[: -1]

Each popped character is re-inserted into need, signaling that it must be placed again later. The slice operation result[: -1] creates a new string without the last character, which is efficient in Python because strings are immutable and the operation works on the underlying memory representation.

Adding the Current Character

After any necessary removals, the current character c is appended to result, and it is marked as satisfied by discarding it from need.

result += c
need.discard(c)

When the loop finishes, result contains the smallest possible subsequence that includes every distinct character exactly once.

Edge Cases Handled

The code gracefully handles inputs where characters repeat many times. By tracking remaining frequencies, it knows whether a larger character can be deferred for a later occurrence, preventing premature inclusion that would break minimality.

When the input string consists of a single unique character, the frequency map starts at one, the while condition never triggers, and the algorithm returns that single character unchanged.

If the input is an empty string, the initial frequency map is empty, need is an empty set, and the loop body never executes, resulting in an empty string being returned.

Strings where characters appear in descending lexicographic order are also covered. The while loop will repeatedly remove previously added characters until the smallest character seen so far becomes the leading element, ensuring the final order is ascending.

Performance Optimizations

The implementation relies on constant-time dictionary lookups for frequency updates and set membership checks, avoiding any nested scans of the input.

Using a defaultdict(int) eliminates the need for explicit existence checks before incrementing counts, streamlining the initial frequency construction.

The need set provides O(1) containment tests to decide whether a character should be processed, allowing the algorithm to skip redundant work for characters that have already been placed.

String slicing (result[: -1]) is employed instead of converting the result to a list and popping, which reduces overhead associated with mutable containers. Because Python strings are immutable, each slice creates a new string, but the overall number of slices is bounded by the number of characters removed, which is at most the length of the input.

The single pass over the input ensures that each character is examined only once for frequency decrement and at most once for inclusion in the result, leading to a tight execution profile.

Overall, the design balances readability with efficient use of Python’s built-in data structures, delivering a solution that operates with minimal auxiliary memory and swift character-level operations.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have a long line of colorful blocks, and each block has a letter written on it. Some letters appear more than once in the line. The goal is to pick out one of each different letter you see, but you have to be very careful about the order. You want to make the shortest, neatest line possible where the letters appear in alphabetical order, like a tiny dictionary.

First, you look at all the blocks to see how many of each letter there are in total. This helps you know if a letter will show up again later if you decide to skip it for now.

You start building your own special row by looking at each block in the original line one by one. If you see a letter that you have not picked yet, you want to put it in your row. But before you add the new block, you look at the last block you placed in your row. If the last block is a letter that comes later in the alphabet than the new block, and you know that the same letter will appear again later in the original line, you take that last block out. You keep doing this until either your row is empty, the last block is earlier in the alphabet than the new block, or there are no more of that letter left to find later.

Once you have checked that, you put the new block at the end of your row and make a note that you have already collected that specific letter. You keep moving through the line until every letter has been picked exactly once and tucked neatly into your row.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 7.56 | σ = 1.17

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java Go TS
LeetcodeHelp C++ Python Java
Progiez C++ Python Java
github BigEggStudy C#
black-shadows C++
charles-wangkai Java
everthis JS
fartem Ruby
fsq C++
Garvit244 Python
JoshCrozier JS
lkwq007 Python
suxrobGM C#
varunu28 Java
wisdompeak C++
withaarzoo C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python, TypeScript
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
everthis JavaScript
fartem Ruby
fsq C++
Garvit244 Python
JoshCrozier JavaScript
lkwq007 Python
suxrobGM C#
varunu28 Java
wisdompeak C++
withaarzoo C++
31 links | 18 authors | 8 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

4 solutions   February 29, 2024

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality