Problem Description

Given a string s, you need to find the lexicographically smallest subsequence that contains every distinct character from s exactly once.

A subsequence is a sequence that can be derived from the original string by deleting some (possibly zero) characters without changing the order of the remaining characters. For example, "ace" is a subsequence of "aebdc".

Lexicographically smallest means the subsequence that would appear first in dictionary order. For instance, "abc" comes before "abd" lexicographically.

The key requirements are:

• The result must be a subsequence of the original string (maintain relative order)
• Every unique character from the original string must appear exactly once in the result
• Among all valid subsequences meeting the above criteria, return the lexicographically smallest one

For example:

• If s = "bcabc", the distinct characters are 'a', 'b', and 'c'. The possible subsequences containing each character once include "bca", "bac", "cab", "abc", etc. Among these, "abc" is the lexicographically smallest, so it's the answer.
• If s = "cbacdcbc", the answer would be "acdb" as it contains all distinct characters ('a', 'b', 'c', 'd') exactly once and is the smallest lexicographical subsequence possible.

Intuition

The challenge is to build the lexicographically smallest subsequence while ensuring we include all distinct characters. The key insight is that we want smaller characters to appear as early as possible in our result.

Consider this: when we encounter a character, we face a decision - should we include it now or wait for a potentially better position later? The answer depends on two factors:

1. Can we safely skip this character because it appears again later?
2. Can we improve our current result by removing some previously added characters?

This naturally leads us to think about using a stack (or similar structure) to build our answer. As we process each character, we can make greedy decisions:

• If we've already included this character, skip it (we only want each character once)
• If the current character is smaller than the last character in our result, we might want to remove the last character and use the current one instead
• But we can only remove a character from our result if it appears again later in the string

The crucial realization is that we need to know the last occurrence position of each character. This allows us to determine whether it's safe to remove a character from our current result - we can only remove it if we'll encounter it again later.

The algorithm becomes: maintain a stack of characters forming our result. For each new character, if it's smaller than the top of the stack AND the top character appears again later, we pop the stack. We keep popping while this condition holds. Then we add the current character (if not already present).

This greedy approach works because at each step, we're making the locally optimal choice that leads to the globally optimal lexicographically smallest subsequence.

Learn more about Stack, Greedy and Monotonic Stack patterns.

Solution Approach

The implementation uses a monotonic stack approach with additional tracking to ensure each character appears exactly once.

Data Structures Used:

1. last: A dictionary that maps each character to its last occurrence index in the string
2. stk: A stack (implemented as a list) to build the result subsequence
3. vis: A set to track which characters are currently in the stack

Algorithm Steps:

1. Preprocessing: Build the last dictionary by iterating through the string and recording the last index where each character appears:

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

2. Main Processing: Iterate through each character with its index:

   for i, c in enumerate(s):

3. Skip Duplicates: If the character is already in our result (tracked by vis), skip it:

   if c in vis:
       continue

4. Maintain Monotonic Property: Before adding the current character, check if we can improve the result by removing larger characters from the stack:

   while stk and stk[-1] > c and last[stk[-1]] > i:
       vis.remove(stk.pop())

   This condition checks:

   • stk: Stack is not empty
   • stk[-1] > c: The top character is lexicographically larger than the current character
   • last[stk[-1]] > i: The top character appears again later in the string (safe to remove)

5. Add Current Character: After potentially removing larger characters, add the current character to the stack and mark it as visited:

   stk.append(c)
   vis.add(c)

6. Build Result: After processing all characters, join the stack to form the final string:

   return "".join(stk)

The algorithm ensures that at each step, we maintain the smallest possible lexicographical order while guaranteeing that all distinct characters will eventually be included. The time complexity is O(n) where n is the length of the string, as each character is pushed and popped from the stack at most once.

Example Walkthrough

Let's trace through the algorithm with s = "cbacdcbc".

Step 1: Preprocessing

• Build last dictionary: {'c': 7, 'b': 6, 'a': 2, 'd': 4}
• Initialize: stk = [], vis = set()

Step 2: Process each character

Index 0, character 'c':

• 'c' not in vis
• Stack is empty, no need to pop
• Push 'c': stk = ['c'], vis = {'c'}

Index 1, character 'b':

• 'b' not in vis
• Check while condition: stk[-1] = 'c' > 'b' is True, and last['c'] = 7 > 1 is True
• Pop 'c': stk = [], vis = {}
• Push 'b': stk = ['b'], vis = {'b'}

Index 2, character 'a':

• 'a' not in vis
• Check while condition: stk[-1] = 'b' > 'a' is True, and last['b'] = 6 > 2 is True
• Pop 'b': stk = [], vis = {}
• Push 'a': stk = ['a'], vis = {'a'}

Index 3, character 'c':

• 'c' not in vis
• Check while condition: stk[-1] = 'a' > 'c' is False
• Push 'c': stk = ['a', 'c'], vis = {'a', 'c'}

Index 4, character 'd':

• 'd' not in vis
• Check while condition: stk[-1] = 'c' > 'd' is False
• Push 'd': stk = ['a', 'c', 'd'], vis = {'a', 'c', 'd'}

Index 5, character 'c':

• 'c' in vis, skip

Index 6, character 'b':

• 'b' not in vis
• Check while condition: stk[-1] = 'd' > 'b' is True, and last['d'] = 4 > 6 is False
• Cannot pop 'd' (it won't appear again)
• Push 'b': stk = ['a', 'c', 'd', 'b'], vis = {'a', 'c', 'd', 'b'}

Index 7, character 'c':

• 'c' in vis, skip

Step 3: Build result

• Join stack: "acdb"

The algorithm successfully builds the lexicographically smallest subsequence containing all distinct characters exactly once. The key insight demonstrated is how we backtrack (pop from stack) when we find a smaller character, but only if we're guaranteed to see the popped character again later.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input string s.

• Creating the last dictionary takes O(n) time as we iterate through the string once.
• The main loop iterates through each character in the string once, which is O(n).
• Inside the loop, each character can be pushed to and popped from the stack at most once throughout the entire execution:
  • The if c in vis check is O(1) with a set.
  • The while loop might seem like it could lead to O(n²) complexity, but each character is pushed once and popped at most once, making the total work across all iterations O(n).
  • Adding to and removing from the set vis are O(1) operations.
• Joining the stack at the end takes O(n) time.

Overall time complexity: O(n) + O(n) + O(n) = O(n)

Space Complexity: O(1) or O(26) = O(1) if we consider only lowercase English letters, otherwise O(k) where k is the number of unique characters.

• The last dictionary stores at most one entry per unique character in the string, which is O(k) where k is the number of unique characters. For lowercase English letters, this is at most 26, hence O(1).
• The stack stk can contain at most all unique characters, which is O(k).
• The set vis similarly stores at most all unique characters, which is O(k).

Overall space complexity: O(k) where k is the number of unique characters in the string, which simplifies to O(1) for a fixed alphabet size.

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

Common Pitfalls

Pitfall 1: Forgetting to Check Future Occurrences Before Removing Characters

The Problem: A common mistake is to greedily remove any character that is lexicographically larger than the current character without checking if it appears later in the string. This can lead to missing characters in the final result.

Incorrect Implementation:

# WRONG: Missing the last occurrence check
while stack and stack[-1] > char:  # Missing: and last_occurrence[stack[-1]] > index
    removed_char = stack.pop()
    visited.remove(removed_char)

Example Where It Fails: For input s = "ecbacba":

• Without the last occurrence check, when we encounter the first 'a', we might remove 'e', 'c', and 'b'
• But 'e' only appears once at the beginning, so removing it means we lose it forever
• The result would be missing the character 'e'

Solution: Always verify that a character appears later before removing it:

while stack and stack[-1] > char and last_occurrence[stack[-1]] > index:
    removed_char = stack.pop()
    visited.remove(removed_char)

Pitfall 2: Not Tracking Visited Characters Properly

The Problem: Without properly tracking which characters are already in the stack, you might add duplicates or incorrectly process the same character multiple times.

Incorrect Implementation:

# WRONG: Not maintaining visited set properly
for index, char in enumerate(s):
    # Missing: if char in visited: continue
    while stack and stack[-1] > char and last_occurrence[stack[-1]] > index:
        stack.pop()  # Missing: visited.remove(stack.pop())
    stack.append(char)
    # Missing: visited.add(char)

Example Where It Fails: For input s = "bcabc":

• Without the visited check, 'b' would be added multiple times
• The result might be "bbac" or "bcabc" instead of "abc"

Solution: Maintain a visited set that accurately reflects what's currently in the stack:

1. Skip characters already in the result
2. Remove from visited when popping from stack
3. Add to visited when pushing to stack

Pitfall 3: Using Wrong Data Structure for Last Occurrence

The Problem: Some might try to check for future occurrences by scanning the remaining string each time, leading to O(n²) time complexity.

Incorrect Implementation:

# WRONG: Inefficient O(n²) approach
for index, char in enumerate(s):
    if char in visited:
        continue
    while stack and stack[-1] > char:
        # Scanning remaining string every time - O(n) operation
        if stack[-1] in s[index+1:]:  # Inefficient!
            removed_char = stack.pop()
            visited.remove(removed_char)
        else:
            break

Solution: Pre-compute the last occurrence of each character in O(n) time:

last_occurrence = {char: index for index, char in enumerate(s)}
# Now checking is O(1): last_occurrence[stack[-1]] > index