Smallest Subsequence Of Distinct Characters - Leetcode Solution

Problem Statement: Given a string s, return the smallest subsequence of s that contains all the distinct characters of s exactly once.

Solution Approach:

Approaching this problem by the following steps:

1. Find the last occurrence of each character in the string, and store it in a dictionary or hash table.

2. Loop through the characters in the string, and for each character, do the following:

   a. If the character is already in the stack, just continue on to the next character.

   b. If the character is not in the stack:

   i. Check to see if the character is smaller than the top character on the stack, and if the top character will appear again later in the string.

   ii. If both of these conditions are satisfied, pop the top character off the stack and continue with the loop.

   iii. Once the conditions are no longer satisfied, push the current character onto the stack.

3. Once the loop is finished, build the result string from the characters on the stack, in the order they were added.

Implementation:

1. Create an empty stack to hold the characters of the smallest subsequence.

2. Create an empty dictionary to hold the last occurrence of each character in the string.

3. Loop through the characters in the string, and for each character, do the following:

   a. Check if the character is already in the stack. If it is, continue loop.

   b. If the character is not in the stack, check if the character is smaller than the top character on the stack, and if the top character will appear again later in the string.

   c. If both the above conditions are satisfied, pop the character on top of the stack. Repeat until these conditions are no longer satisfied.

   d. Once these conditions are no longer satisfied, push the character onto the stack and update the position of the last occurrence of this character in the dictionary.

4. Concatenate the characters on the stack to form the smallest subsequence.

Code:

A sample code to solve this problem in Python is given below:

def smallestSubsequence(s: str) -> str:

last_occurrence = {c: i for i, c in enumerate(s)}

stack = []

for i, c in enumerate(s):

    if c in stack:
        continue

    while stack and stack[-1] > c and i < last_occurrence[stack[-1]]:
        stack.pop()

    stack.append(c)

return ''.join(stack)

Time complexity: O(n) Space complexity: O(n)

Explanation:

The time complexity of the above solution is O(n), as we loop through the input string once.

The space complexity of the above solution is also O(n), as we create a dictionary and stack, each with size n.

In the above solution, we create a dictionary to store the last occurrence of each character in the input string. Then we iterate through the input string, and for each character, we check if it is already in the stack. If it is, we continue to the next character. If not, we check if it is smaller than the last character on the stack, and if the last character on the stack will appear again later in the string. If both conditions are satisfied, we pop the top character off the stack. We repeat this until either condition is no longer satisfied, and then push the current character onto the stack. Finally, we concatenate the characters on the stack to form the smallest subsequence.

1