Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Remove Duplicate Letters (medium)

Problem Statement

Given a string s, remove duplicate letters so that every letter that appears in s appears exactly once in the result. You may only delete characters. The letters that survive keep the order they had in s.

Among all the results you can reach that way, return the one that is smallest in lexicographical order.

A string is in the smallest lexicographical order if it appears first in a dictionary. For example, "abc" is smaller than "acb" because "abc" comes first alphabetically.

Note that this does not mean sorting the letters. "zabccde" gives

.....

.....

.....

Like the course? Get enrolled and start learning!
V

viniciuslopeslps

· 2 years ago

I do know exactly how to sort in smallest lexicographical order.

to my mind, the sort of string should already do this but the example of zabccde should return zabccde and not abcdez.

Can you explain a little more about it?

Show 2 replies
P

Pete Stenger

· 2 years ago

# I found it easier to think about using the rightmost position of each character.
# If we haven't added the character to the  string, and doing so would violate lexicographical order, remove all characters currently in the string that have a later # rightmost position than the current index. 
# This ensures that we have the smallest lexicographical ordering.
from collections import Counter, defaultdict

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        # Last position in string
        last = {}
        for i in range(len(s) - 1, -1, -1):
            if s[i] not in last:
                last[s[i]] = i


        final = []
        seen = defaultdict(bool)
        for i, char in enumerate(s):
            # However, we should only do that processing when
Show 1 reply
L

lejafilip

· 2 years ago

Not trivial to got greedy solution.

Show 2 replies

Reading Progress

0%

Vote for new content