Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Remove Duplicate Letters (medium)

Problem Statement

Given a string s, remove all duplicate letters from the input string while maintaining the original order of the letters.

Additionally, the returned string should be the smallest in lexicographical order among all possible results.

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.

Examples:

    • Input: "babac"
    • Expected Output: "abc"
    • Justification:
      • After removing 1 b and 1 `a

.....

.....

.....

Like the course? Get enrolled and start learning!
L

lejafilip

· 2 years ago

Not trivial to got greedy solution.

Show 1 reply
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
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 1 reply