Python solution with detailed explanation

  • 0


    Remove Duplicate Letters

    Brute Force

    • At every index in string, we can either choose the character or ignore the character.
    class Solution(object):
        def helper(self, idx, s, so_far, N):
            if len(so_far) == N:
                ssofar = "".join(so_far)
                if self.min_so_far == None:
                    self.min_so_far = ssofar
                    self.min_so_far = min(self.min_so_far, ssofar)
            elif idx == len(s):
                ch = s[idx]
                if ch not in so_far:
                    self.helper(idx+1, s, so_far, N)
        def removeDuplicateLetters(self, inp):
            :type s: str
            :rtype: str
            self.min_so_far = None
            N = len(set(inp))
            self.helper(0, inp, [], N)
            return self.min_so_far

    Optimized N^2 Solution

    • N^2 solution will be to trigger a search for all characters smaller than or equal to ch at the last occuring index for ch. So if ch = "u" is at index, 2,5,7,9; then at index 9, find all characters less than equal to u in increasing order.
    • We do the above by sorting all characters with their indices from start to index of "u". In this increasing set, we find the longest run such that each successive index is larger than previous. Make sure to handle the case of duplicates in this set - we want the first occurence to build the longest chain.
    • Another important variable is "start". This indicates the position where we will start searching when we next hit a single frequency character. We want to start from the position we left.
    • Another approach to search for candidates before last occurence of a character could be to search in sorted order of unique characters. Find all unique characters. Sort them. Then sequentially search for each of them within start to idx+1. Apply appropriate optimizations.
    class Solution(object):
        def removeDuplicateLetters(self, s):
            :type s: str
            :rtype: str
            idx_map = {ch:idx for idx,ch in enumerate(s)}
            ss = sorted(idx_map.items(), key=lambda x:x[1])
            result, included = [], set([])
            start = 0
            for ch, idx in ss:
                if ch in included:
                candidates = []
                for i in range(start,idx+1):
                    c = s[i]
                    if c not in included and c <= ch :
                candidates.sort(key=lambda x:x[1])
                for i,x in candidates:
                    if x not in included and (result == [] or result[-1][0] < i):
                if result:
                    start = result[-1][0] + 1
            return "".join([b for a,b in result])

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.