Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1159. Smallest Subsequence of Distinct Characters

My accepted Python solution to LeetCode problem 1159, Smallest Subsequence of Distinct Characters, running in 3ms.

  • Difficulty: Medium
  • Python
  • Runtime 3ms
  • Memory 17.3MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 3ms, memory 17.3MB, accepted 2026-01-02.

python
class Solution:
    def smallestSubsequence(self, s: str) -> str:
        # Count remaining occurrences of each character
        remaining = {}
        for c in s:
            remaining[c] = remaining.get(c, 0) + 1
        
        stack = []
        in_stack = set()
        
        for c in s:
            remaining[c] -= 1
            
            # If character already in result, skip it
            if c in in_stack:
                continue
            
            # While stack is not empty and current char is smaller
            # and the top char appears later, pop it
            while stack and c < stack[-1] and remaining[stack[-1]] > 0:
                in_stack.remove(stack.pop())
            
            stack.append(c)
            in_stack.add(c)
        
        return ''.join(stack)

Source