Leetcode 1081: Smallest Subsequence of Distinct Characters
You are given a string s, and your task is to return the lexicographically smallest subsequence of s that contains all the distinct characters of s exactly once. The subsequence must be in the same order as the original string, but the characters should not repeat.
Problem
Approach
Steps
Complexity
Input: The input consists of a string s that contains lowercase English letters.
Example: Input: s = "zabcde"
Constraints:
• 1 <= s.length <= 1000
• s consists of lowercase English letters.
Output: The output should be the lexicographically smallest subsequence containing all the distinct characters of s exactly once.
Example: Output: "abcde"
Constraints:
• The subsequence should preserve the order of the original string.
Goal: The goal is to find the lexicographically smallest subsequence of the string containing each distinct character exactly once while maintaining the order.
Steps:
• 1. Count the last occurrence index of each character in the string.
• 2. Traverse the string and construct the result by considering whether to add each character based on its lexicographical order and ensuring that it doesn't repeat.
Goal: The solution must efficiently handle strings with up to 1000 characters.
Steps:
• 1 <= s.length <= 1000
• s consists of lowercase English letters.
Assumptions:
• The input string is non-empty and contains lowercase English letters.
• Input: Input: s = "bcabc"
• Explanation: In this example, the lexicographically smallest subsequence that contains all the distinct characters exactly once is "abc".
• Input: Input: s = "cbacdcbc"
• Explanation: In this case, the lexicographically smallest subsequence is "acdb".
Approach: We can solve this problem using a greedy algorithm that ensures the lexicographically smallest subsequence. By keeping track of the characters we have seen and the last occurrence of each character, we can decide which character to add to the result at each step.
Observations:
• We need to ensure that each character appears only once in the subsequence and that the subsequence is the lexicographically smallest.
• Using a stack can help us maintain the order and ensure the smallest lexicographical subsequence.
Steps:
• 1. Create a stack to build the result subsequence.
• 2. Traverse the string from left to right.
• 3. For each character, if it hasn't been added to the subsequence, check whether it can be added by comparing with the top character of the stack.
• 4. If the current character is smaller than the top character and the top character appears later, pop the stack to ensure the subsequence is lexicographically smaller.
• 5. Add the current character to the stack and mark it as seen.
Empty Inputs:
• If the string is empty, return an empty string.
Large Inputs:
• The solution must handle large strings (up to 1000 characters) efficiently.
Special Values:
• If the string consists of the same repeated character, the result should be that character alone.
Constraints:
• The solution should be optimized to handle the input string within the provided constraints.
string smallestSubsequence(string s) {
int n = s.size();
string res = "";
vector<int> in(26, 0), seen(26, 0);
for (int i = 0; i < n; i++)
in[s[i] - 'a'] = i;
vector<int> stk;
for (int i = 0; i < n; i++) {
int c = s[i] - 'a';
if (seen[c]++ > 0) continue;
while (!stk.empty() && stk.back() > c && i < in[stk.back()]) {
seen[stk.back()] = 0;
stk.pop_back();
}
stk.push_back(c);
}
for (int i = 0; i < stk.size(); i++)
res += ('a' + stk[i]);
return res;
}
};
1 : Function Definition
string smallestSubsequence(string s) {
This line defines the function `smallestSubsequence`, which takes a string `s` as input and will return the smallest subsequence of characters from `s`.
2 : Variable Initialization
int n = s.size();
The size of the string `s` is stored in the variable `n`.
3 : Result Initialization
string res = "";
An empty string `res` is initialized to build the result subsequence.
4 : Vector Initialization
vector<int> in(26, 0), seen(26, 0);
Two vectors are initialized: `in` stores the last occurrence index of each character, and `seen` tracks whether a character is already in the result subsequence.
5 : Loop - Storing Last Occurrence
for (int i = 0; i < n; i++)
This loop iterates over each character in the string `s`.
6 : Store Last Occurrence
in[s[i] - 'a'] = i;
For each character in `s`, the index of its last occurrence is stored in the `in` vector.
7 : Vector Initialization - Stack
vector<int> stk;
An empty vector `stk` is initialized to act as a stack for the characters that will form the smallest subsequence.
8 : Loop - Main Logic
for (int i = 0; i < n; i++) {
This loop processes each character in the string `s`.
9 : Character Calculation
int c = s[i] - 'a';
This line calculates the index `c` of the character `s[i]` relative to 'a', where 'a' corresponds to 0, 'b' to 1, and so on.
10 : Skip Duplicates
if (seen[c]++ > 0) continue;
This checks if the character `s[i]` has already been added to the result subsequence. If it has, it skips the current iteration.
11 : Remove Ineligible Characters
while (!stk.empty() && stk.back() > c && i < in[stk.back()]) {
This while loop removes characters from the stack if they are lexicographically larger than the current character `c` and can still appear later in the string.
12 : Reset Seen for Popped Characters
seen[stk.back()] = 0;
This resets the `seen` status for the character that is being removed from the stack.
13 : Pop Character from Stack
stk.pop_back();
This removes the character from the stack as it is no longer needed in the result subsequence.
14 : Push Current Character
stk.push_back(c);
The current character `c` is pushed onto the stack for inclusion in the subsequence.
15 : Build Result Subsequence
for (int i = 0; i < stk.size(); i++)
This loop iterates over the stack to build the result subsequence from the characters stored in the stack.
16 : Construct Result String
res += ('a' + stk[i]);
For each character in the stack, its corresponding character (using the index) is added to the result string `res`.
17 : Return Result
return res;
The resulting subsequence `res` is returned as the output.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The algorithm processes each character of the string once, making the time complexity linear in terms of the length of the string.
Best Case: O(1)
Worst Case: O(26)
Description: The space complexity is O(26) because the maximum number of distinct characters is 26, corresponding to the lowercase English alphabet.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus