Stack Topological Sort Simulation
Proficient Level

Implement the removeDuplicateLettersSmallest method that removes duplicate letters and returns the smallest possible result.

You are given a lowercase string. Remove duplicate letters so that every distinct character appears exactly once.

Among all valid results, return the lexicographically smallest string. The relative order of characters must follow their order in the original string.

Example 1
Input:
text (string) = bcabc
Return:
(string) abc
Example 2
Input:
text (string) = cbacdcbc
Return:
(string) acdb
Example 3
Input:
text (string) = abacb
Return:
(string) abc

Use a monotonic stack with character frequency tracking.

Count how many times each character still remains to the right. While processing a character, if it is already in the stack, skip it. Otherwise, remove larger characters from the top of the stack when they will appear again later. Then push the current character.

This keeps the result as small as possible without losing any required character.

Pseudocode:

function removeDuplicateLettersSmallest(text):
    remaining = frequency of each character
    used = empty set
    stack = empty stack
    for each character ch in text:
        remaining[ch]--
        if ch is in used:
            continue
        while stack is not empty and stack.top > ch and remaining[stack.top] > 0:
            removed = stack.pop()
            remove removed from used
        push ch into stack
        add ch to used
    return characters from stack as string
Run your code to see the result.