Problem Breakdown
We need to find a subsequence of s that includes every unique character present in the string exactly once. Among all such valid subsequences, we must return the one that is lexicographically smallest (comes first alphabetically).
Key Constraints:
- Subsequence: Relative order from original string must be preserved; no reordering allowed.
- Distinctness: Each unique character in
sappears exactly once in the result, regardless of how many times it appeared ins. - Lexicographical Order: We prioritize smaller characters appearing earlier in our output.
Intuition
A brute-force approach generating all subsequences is exponential (). Instead, we can use a greedy strategy with backtracking capabilities via a stack:
- Greedy Choice: Always try to place the smallest available character as early as possible.
- Backtracking (Stack Popping): If our current result ends with a larger character than the new incoming character
c, and that larger character appears again later ins(so we can add it back safely), we should remove the larger character from our stack to placecearlier for lexicographical gain. - Tracking: We need to know if characters appear later (
last_occurrence) so we don’t discard a necessary unique instance prematurely, and we use a set/boolean array to track which characters are currently in our subsequence (to ensure distinctness).
Approach
- Preprocessing: Calculate the last index of every character in
s. This allows us to determine if a popped character can be re-added later. - Stack Construction: Iterate through string
swith an indexi:- If current char is already included (in our stack), skip it for now. We only care about the first instance we keep, unless that specific instance was removed from the stack due to a smaller character coming up later.
- Optimization Check: While the top of the stack contains a character larger than
current_charAND that top character appears again in the string after indexi:- Pop the stack (remove it).
- Mark as not visited so we can add it back later.
- Add current char to stack and mark as visited.
- Result: Join the characters remaining in the stack at the end of iteration.
Complexity Analysis
- Time Complexity: , where is the length of string
s. We traverse the string once. Each character enters the stack exactly once and leaves it at most once (amortized constant time per operation). Dictionary lookups are . - Space Complexity: , where is the size of the alphabet (26 for lowercase English letters). We use a map for last occurrences (), a set for visited characters (), and a stack that holds at most all unique characters (). Since is constant relative to input length, this can be considered space complexity in the context of LeetCode constraints.
Solution
class Solution:
def smallestSubsequence(self, s: str) -> str:
# Map each character to its last occurrence index in the input string
last_occurrence = {c: i for i, c in enumerate(s)}
stack = []
visited = set() # To track characters currently included in our subsequence
for i, char in enumerate(s):
if char not in visited:
# While the current character is smaller than the top of the stack,
# and the top element appears later again (so we can pop it safely),
# remove the larger element from the stack to maintain lexicographical order.
while stack and last_occurrence[stack[-1]] > i:
removed_char = stack.pop()
visited.remove(removed_char)
stack.append(char)
visited.add(char)
return "".join(stack)
# Example usage for verification (not part of the class solution):
# sol = Solution()
# print(sol.smallestSubsequence("bcabc")) # Output: "abc"
# print(sol.smallestSubsequence("cbacdcbc")) # Output: "acdb"
Edge Cases Handled
- Single Character Input: The loop runs once, stack gets the char, returns it. Correct.
- All Distinct and Sorted (e.g.,
s = "abc"): No characters are popped becausestack[-1] < currentis always true or condition fails; result matches input. Correct. - **Duplicates Only (e.g.,
"aaaa")**:** First 'a' pushed, subsequent 'a's skipped byvisited`. Result “a”. Correct. - Reverse Order with Duplicates (Example 2): Logic correctly pops larger characters from stack if they appear later in the string to accommodate smaller ones earlier.