#3816
Lexicographically Smallest String After Deleting Duplicate Characters
HardHash TableStringStackGreedyMonotonic StackHash MapArray
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n) |
| Space | O(1) | O(n) |
💡
Intuition
Time O(n)Space O(n)
Use a stack to maintain the order of characters while ensuring uniqueness and lexicographical order.
⚙️
Algorithm
3 steps- 1Step 1: Count occurrences of each character.
- 2Step 2: Use a stack to build the result string, ensuring each character is added only once.
- 3Step 3: Remove characters from the stack if the current character is smaller and can still appear later.
solution.py13 lines
1def smallestString(s):
2 stack = []
3 seen = set()
4 count = {c: s.count(c) for c in s}
5 for c in s:
6 count[c] -= 1
7 if c in seen:
8 continue
9 while stack and stack[-1] > c and count[stack[-1]] > 0:
10 seen.remove(stack.pop())
11 stack.append(c)
12 seen.add(c)
13 return ''.join(stack)ℹ
Complexity note: The algorithm processes each character once, leading to linear time complexity. The space is used for the stack and count arrays.
- 1Each character must appear only once.
- 2Lexicographical order can be maintained using a stack.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.