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

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)

--

--

--

Data Engineering & Analytics

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Iris S

Iris S

Data Engineering & Analytics

More from Medium