Given a string s
, return the lexicographically smallest subsequence of s
that contains all the distinct characters of s
exactly once.
Example 1:
Input: s = "bcabc"
Output: "abc"
Example 2:
Input: s = "cbacdcbc"
Output: "acdb"
Constraints:
1 <= s.length <= 1000
s
consists of lowercase English letters.A brute force approach would involve generating all possible subsequences of the input string s
, filtering out those that do not contain all distinct characters exactly once, and then finding the lexicographically smallest among the remaining subsequences. This approach is highly inefficient because the number of subsequences grows exponentially with the length of the string.
A more efficient approach involves using a stack and a greedy algorithm. The idea is to iterate through the string and maintain a stack of characters that form the lexicographically smallest subsequence seen so far. For each character, we check if it's already in the stack. If not, we compare it with the top of the stack. If the current character is smaller than the top of the stack and the top of the stack appears later in the string, we pop the top of the stack and push the current character. We repeat this process until the stack is empty or the current character is not smaller than the top of the stack or the top of the stack does not appear later in the string.
last_occurrence
map to store the last index of each character in the string.seen
set to keep track of characters currently in the stack.stack
.s
with index i
and character char
:
char
is in seen
, skip it.stack
is not empty, the top of the stack
is greater than char
, and last_occurrence[stack[-1]] > i
:
stack
from seen
.stack
.char
to seen
.char
onto the stack
.stack
.def smallestSubsequence(s: str) -> str:
last_occurrence = {}
for i, char in enumerate(s):
last_occurrence[char] = i
stack = []
seen = set()
for i, char in enumerate(s):
if char in seen:
continue
while stack and stack[-1] > char and last_occurrence[stack[-1]] > i:
removed_char = stack.pop()
seen.remove(removed_char)
stack.append(char)
seen.add(char)
return "".join(stack)
Let's trace the execution with the input s = "cbacdcbc"
last_occurrence = {'c': 7, 'b': 6, 'a': 2, 'd': 4}
stack = []
, seen = set()
i = 0
, char = 'c'
. Stack is empty, so stack.append('c')
, seen = {'c'}
i = 1
, char = 'b'
. 'c' > 'b'
and last_occurrence['c'] > 1
, so pop 'c'. stack = []
, seen = {}
. stack.append('b')
, seen = {'b'}
i = 2
, char = 'a'
. 'b' > 'a'
and last_occurrence['b'] > 2
, so pop 'b'. stack = []
, seen = {}
. stack.append('a')
, seen = {'a'}
i = 3
, char = 'c'
. Stack is not empty but 'a' < 'c'. stack.append('c')
, seen = {'a', 'c'}
i = 4
, char = 'd'
. Stack is not empty but 'c' < 'd'. stack.append('d')
, seen = {'a', 'c', 'd'}
i = 5
, char = 'c'
. char in seen
, skip.i = 6
, char = 'b'
. 'd' > 'b'
and last_occurrence['d'] > 6
, so pop 'd'. stack = ['a', 'c']
, seen = {'a', 'c'}
. 'c' > 'b'
and last_occurrence['c'] > 6
, so pop 'c'. stack = ['a']
, seen = {'a'}
. stack.append('b')
, seen = {'a', 'b'}
i = 7
, char = 'c'
. char in seen
, skip."".join(['a', 'b', 'c', 'd']) = "acdb"
last_occurrence
map, seen
set, and the stack
.