Leetcode Problem 1081. Smallest Subsequence of Distinct Characters

1081. Smallest Subsequence of Distinct Characters

Leetcode Solutions

Monotonic Stack Approach

  1. Create a stack to store the characters for the result subsequence.
  2. Create a boolean array seen to indicate if a character is in the stack.
  3. Create an array last to store the last occurrence index of each character.
  4. Iterate through the characters of the string s.
    • If the current character is already in the stack, continue to the next iteration.
    • While the stack is not empty and the top character of the stack is greater than the current character and the top character appears later in the string, pop the stack and mark the character as not seen.
    • Push the current character onto the stack and mark it as seen.
  5. Convert the stack to a string in reverse order to get the result.
UML Thumbnail

Greedy Approach with Last Occurrence Map

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...