Remove Duplicate Letters - Solution
Solutions and explanations
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
seen = set()
last_occ = {}
for idx, ele in enumerate(s):
last_occ[ele] = idx
stack = []
for idx, ele in enumerate(s):
if ele in seen:
continue
while stack and stack[-1] > ele and last_occ[stack[-1]] > idx:
removed_ele = stack.pop()
seen.remove(removed_ele) # Remove from seen set, as it's not in stack anymore
stack.append(ele)
seen.add(ele)
return "".join(stack)
Complexity Analysis
Here, n is the length of the input string.
- Time Complexity:
O(n)- All characters in the string are traversed once, performing constant work for building the hashmap as well as stack push and pop operations.
- Space Complexity:
O(n)- The stack, hashset to track seen elements, and dictionary storing last ocuurence store at most
ncharacters.
- The stack, hashset to track seen elements, and dictionary storing last ocuurence store at most