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) =
bcabcReturns (string)
abcExample 2
Input
text (string) =
cbacdcbcReturns (string)
acdbExample 3
Input
text (string) =
abacbReturns (string)
abcUse 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 stringReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run