1081. Smallest Subsequence of Distinct Characters

Problem Description

The problem requires us to find a specific type of subsequence from a given string s. A subsequence is a sequence that can be derived from the original string by deleting some or no characters without changing the order of the remaining characters. The goal is to determine the lexicographically smallest subsequence that contains every distinct character of s exactly once.

Let's break it down:

• Lexicographically smallest: This means the sequence that would appear first if all possible subsequences were sorted in dictionary order.
• Subsequence: This is a sequence that can be derived from another sequence by deleting some or none of the elements without changing the order of the remaining elements.
• Contains all the distinct characters of s exactly once: The subsequence must have all unique characters that appear in s, and none of these characters should be repeated.

This is like a puzzle where you need to choose characters, ensuring that you include each unique character at least once, but you can't choose a later character if it will cause an earlier unique character to never appear again in the remaining part of the string s.

Intuition

To find the lexicographically smallest subsequence, we should take the smallest available character unless taking it would prevent us from including another distinct character later on. We can use a stack to keep track of the characters in the current subsequence as we iterate through the string. If we can add a smaller character and still have the opportunity to add the characters currently in the stack later, we should do that to ensure our subsequence is the smallest possible lexicographically.

The intuition to make this efficient is as follows:

• Track the last occurrence of each character, so we know if we'll see a character again in the future.
• Use a stack to maintain the characters of the current smallest subsequence.
• Make use of a set to quickly check if a character is already in our stack (and hence, in our current smallest subsequence).
• When we consider adding a new character, check if it is smaller than the last one on the stack, and if we'll encounter the last one on the stack again later (thanks to our tracking of the last occurrence).
• If both conditions are true, we can safely pop the larger character off the stack and remove it from our set without fearing that we won't have it in our subsequence.

By following these steps, we can build the smallest subsequence as we iterate through the string s once.

Learn more about Stack, Greedy and Monotonic Stack patterns.

Solution Approach

The solution uses a greedy algorithm with a stack to generate the lexicographically smallest subsequence. Here is a step-by-step explanation of how the code makes use of this approach:

1. Track the Last Occurrence: We need to know the last position at which each character appears in the string. This is essential to decide whether we can drop a character from the stack for a smaller one. The last dictionary is used to store the last index for every character using a dictionary comprehension: last = {c: i for i, c in enumerate(s)}.

2. Stack for Current Smallest Subsequence: A stack data structure is ideal for maintaining the current sequence of characters. As we iterate through the string, characters are pushed onto the stack if they can potentially be part of the lexicographically smallest subsequence. The stack, stk, is initialized as an empty list [].

3. Set for Visited Characters: To ensure that each character is added only once to the subsequence, a set vis is used to track the characters that are already present in the stack.

4. Iterate Over the String: We iterate over each character c and its index i in the string using for i, c in enumerate(s). If the character has already been visited, we continue to the next iteration with continue.

5. Character Comparison and Stack Pop: This is where the greedy algorithm comes into play. For the current character c, we check if the stack is not empty and the char at the top of the stack is greater than c, and also if the character at the top of the stack occurs later in the string (last[stk[-1]] > i). If all these conditions are true, it means we can pop the top of the stack to make our subsequence lexicographically smaller and we are sure that this character will come again later, thanks to our last occurrence tracking. We pop the character from stack and remove it from vis set.

6. Add the Current Character to the Stack and Visited Set: After making sure the characters on the stack are in the correct lexicographical order and popping those that aren't, we can safely push the current character onto the stack and mark it as visited by adding it to the vis set with vis.add(c).

7. Build and Return the Result: At the end, the stack stk contains the lexicographically smallest subsequence. We join all the characters in the stack to form a string and return it with return "".join(stk).

By using a stack along with a set and a last occurrence tracking dictionary, the given Python code efficiently computes the lexicographically smallest subsequence that contains all distinct characters of the input string s exactly once.

Example Walkthrough

Let's consider a simple example to illustrate the solution approach with the string s = "cbacdcbc". We want to find the lexicographically smallest subsequence which contains every distinct character exactly once.

1. Track the Last Occurrence: First, we create a dictionary to track the last occurrence of each character:

   • last occurrence of 'c' at index 7
   • last occurrence of 'b' at index 6
   • last occurrence of 'a' at index 2
   • last occurrence of 'd' at index 4 So, last = {'c': 7, 'b': 6, 'a': 2, 'd': 4}.

2. Stack for Current Smallest Subsequence: We initialize an empty stack stk = [] to keep track of the subsequence characters.

3. Set for Visited Characters: We also have a set vis = {} to mark characters that we have already seen and added to the stack.

4. Iterate Over the String: We iterate over each character in "cbacdcbc". Let's go through this process step by step:

   i. On encountering the first 'c', it is not in vis, so we add 'c' to stk and vis.

   ii. Next, 'b' is not in vis, so we add 'b' to stk and vis. stk now contains ['c', 'b'].

   iii. 'a' is not in vis, so we add 'a' to stk. However, 'a' is smaller than 'b' and 'c', and both 'b' and 'c' will come later in the string. We pop 'b' and 'c' from the stack and remove them from vis. Then, add 'a' to stk and vis. stk now contains ['a'].

   iv. 'c' comes again, we add it back since 'a' < 'c' and 'c' is not in vis. stk now contains ['a', 'c'].

   v. 'd' is encountered, not in vis, so we add it to stk. stk now contains ['a', 'c', 'd'].

   vi. Next, we see another 'c'. It's already in vis, so we skip it.

   vii. 'b' comes next, is not in vis, and is less than 'd'. Since 'd' appears again later (we know from our last occurrence dictionary), we will pop 'd' from stk and remove it from vis, and add 'b' instead. stk now contains ['a', 'c', 'b'].

   viii. Lastly, 'c' comes again, but it is in vis, so we skip it.

5. Character Comparison and Stack Pop: Throughout the iteration, whenever we meet a smaller character, we check if we can pop the larger ones before it, as described above.

6. Add the Current Character to the Stack and Visited Set: We've been doing this in each iteration whenever necessary.

7. Build and Return the Result: At the end, stk contains the lexicographically smallest subsequence. We join the elements of the stack to get "acb", which is our final answer.

We successfully found the lexicographically smallest subsequence "acb" that contains every distinct character of s exactly once.

Solution Implementation

Time and Space Complexity

Time Complexity

The provided code's time complexity can be analyzed based on the number of iterations and operations that are performed:

1. Building the last dictionary: This takes O(n) time, where n is the length of string s, as we go through every character of the string once.

2. Iterating through string s: The main for loop runs for every character, so it is O(n). However, we must also consider the nested while loop.

3. The nested while loop: Although there is a while loop inside the for loop, each element is added to the stk only once because of the vis set check, and each element is removed from stk only once. This means, in total, the while loop will run at most n times for the entire for loop. This does not change the overall time complexity which remains O(n).

Combining these steps, the overall time complexity is O(n) where n is the length of the input string s.

Space Complexity

Analyzing the space used by the code:

1. The last dictionary: The dictionary holds a mapping for each unique character to its last occurrence in s. In the worst case, where all characters are unique, it will hold n entries, which leads to O(n) space.

2. The stk list: As with the dictionary, in the worst case, it may hold all characters if they are all unique, leading to O(n) space.

3. The vis set: This also, in the worst-case scenario, will hold n entries for n unique characters in s, using O(n) space.

Considering all the auxiliary space used, the overall space complexity is O(n).

Putting it all together in the markdown template:

1
2
3### Time Complexity
4
5The time complexity of the code is `O(n)`, where `n` is the length of the given string `s`. This is due to the fact that the for loop will iterate `n` times and the nested while loop, in combination with the stack operations and the set checks, will still result in a linear number of operations in total across all iterations.
6
7### Space Complexity
8
9The space complexity of the code is `O(n)` as well, due to the storage requirements of the `last` dictionary, the `stk` list, and the `vis` set, all of which in the worst case scale linearly with the number of characters `n` in the string `s`.

Learn more about how to find time and space complexity quickly using problem constraints.