Highlight
- Usage of hashmap to keep track of the last index of a character
- Understand the concept of ‘lexicographically smallest’
- Usage of a stack to keep track of the result; compare current character and the tail of the stack
Goal
- Return the lexicographically smallest subsequence of
s
that contains all the distinct characters ofs
exactly once. - Output doesn’t have to be consecutive substrings
Strategy
- Use hash table to store the latest index of each character
- Iterate through the string; use a stack to store the visited character
- If a character is in res, use continue to skip the subsequent steps
- Otherwise, check if the current character is 1) smaller than the last element of the stack, 2) the index of the stack[-1] in the hashmap is larger than the current index, which means we will encounter that character again later, we can safely pop this stack[-1]
- append the current character
Complexity
- Time: we are iterate through the string twice (create hashmap + create output string) → O(N)
- Space: we created a Hashmap & the answer array → O(N)
Code
class Solution:
def smallestSubsequence(self, s: str) -> str:
d = {}
for idx, i in enumerate(s):
d[i] = idx
res = []
for idx, i in enumerate(s):
if i in res:
continue
while res and i < res[-1] and idx < d[res[-1]]:
res.pop()
res.append(i)
return ''.join(res)