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
Difficulty
and has an acceptance rate of about 61% (100k+ submissions).
Typical patterns to solve this problem:
- Greedy
- Monotonic Stack
- Stack
- String
AI Disclaimer
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.
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.
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.
Code Quality
Complexity Analysis
Other Solutions
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++ |
Videos
Similar Problems
- problem 1673: Find the Most Competitive Subsequence
Solved On The Same Day
- problem 1042: Flower Planting With No Adjacent
- problem 1104: Path In Zigzag Labelled Binary Tree
- problem 1192: Critical Connections in a Network
Extra
- 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