Skip to Content

Remove Duplicates Letters

Home | Coding Interviews | Greedy Algorithms | Remove Duplicates Letters

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

#Solution 1
count = Counter(s) # initialize frequency hashmap
st = []
taken = set()
for char in s:
	if char not in taken:
		# check if there are any more instances of the evicting character
		while st and st[-1] > char and count[st[-1]] > 0:
			taken.remove(st.pop())
		st.append(char)
		taken.add(char)
	count[char] -= 1 # finish processing this character
return ''.join(st)

#Solution 2: Another solution written in slightly different way
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        stack = []
        
        for idx, character in enumerate(s):
            if not stack:
                stack.append(character)
            elif character in stack:
                continue
            else:
                while stack and (character < stack[-1]):
                    if stack[-1] in s[idx + 1:]:
                        _ = stack.pop()
                    else:
                        break
                        
                stack.append(character)
                
        return ''.join(stack)

Another explanation of the same method

Posted by Jamie Meyer 3 months ago

Related Problems

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time, n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there's a constraint: identical tasks must be separated by at least n intervals due to cooling time.

Return the minimum number of intervals required to complete all tasks.

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.

We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

Given a positive integer n, return a string representing the smallest positive integer such that the product of its digits is equal to n, or "-1" if no such number exists.