[HT+Stack] LC 1081. Smallest Subsequence of Distinct Characters

Smallest Subsequence of Distinct Characters - LeetCode

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 of s 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)