Python solution with detailed explanation


  • 0
    G

    Solution

    Remove Duplicate Letters https://leetcode.com/problems/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
                else:
                    self.min_so_far = min(self.min_so_far, ssofar)
            elif idx == len(s):
                return
            else:
                ch = s[idx]
                if ch not in so_far:
                    so_far.append(ch)
                    self.helper(idx+1, s, so_far, N)
                    so_far.pop()
                self.helper(idx+1,s,so_far,N)
            return
        
        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.
    • https://discuss.leetcode.com/topic/31404/a-short-o-n-recursive-greedy-solution/2
    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:
                    continue
                candidates = []
                for i in range(start,idx+1):
                    c = s[i]
                    if c not in included and c <= ch :
                        candidates.append((i,c))
                candidates.sort(key=lambda x:x[1])
                for i,x in candidates:
                    if x not in included and (result == [] or result[-1][0] < i):
                        result.append((i,x))
                        included.add(x)
                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.