Given an integer array of digits, return the largest multiple of three that can be formed by concatenating some of the given digits in any order.
Since the answer may not fit in an integer data type, return the answer as a string.
If there is no answer return an empty string.
 
Example 1:
Input: digits = [8,1,9]
Output: "981"

Example 2:
Input: digits = [8,6,7,1,0]
Output: "8760"

Example 3:
Input: digits = [1]
Output: ""

Example 4:
Input: digits = [0,0,0,0,0,0]
Output: "0"

 
Constraints:

1 <= digits.length <= 10^4
0 <= digits[i] <= 9
The returning answer must not contain unnecessary leading zeros.

Difficulty: interview

Starter code:

class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        

Solutions:
class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        counts = Counter(digits)
        m = sum(digits) % 3
        if m:
            if counts[m] + counts[m+3] + counts[m+6]:
                counts[min([m+i for i in [0,3,6] if counts[m+i]])] -= 1
            else:
                counts[min([i-m for i in [3,6,9] if counts[i-m]])] -= 1
                counts[min([i-m for i in [3,6,9] if counts[i-m]])] -= 1
                
        ans = ''
        for i in range(9, -1, -1):
            if not ans and not counts[i]:
                continue
            ans += str(i) * counts[i]
        if ans:
             return ans.lstrip('0') or '0'
        return ''
        
        


class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        
        heaps, total = [[], [], []], 0
        
        for digit in digits:
            total += digit
            heapq.heappush(heaps[digit % 3], str(digit))
        
        if r := (total % 3):
                if heaps[r]:
                    heapq.heappop(heaps[r])
                elif len(heaps[-r]) > 1:
                    heapq.heappop(heaps[-r])
                    heapq.heappop(heaps[-r])
        
        if any(heaps):
            return str(int(''.join(sorted(sum(heaps, []), reverse=True))))
        return ''

class Solution:
    def largestMultipleOfThree(self, d: List[int]) -> str:
        d1 = sorted([i for i in d if i%3 ==1])
        d2 = sorted([i for i in d if i%3 ==2])
        d3 = [i for i in d if i%3 ==0]
        if sum(d) % 3 == 1:
            if len(d1) != 0:
                res = d1[1:] + d2 + d3
            else:
                res = d2[2:]+ d3
        elif sum(d) % 3 == 2:
            if len(d2) != 0:
                res = d1 + d2[1:] + d3
            else:
                res = d1[2:] +d3
        else:
            res = d
        res.sort(reverse = True)
        if not res: return ''
        return str(int(''.join([str(i) for i in res])))

class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        mod_gap = sum(digits) % 3
        if mod_gap == 0:
            answer = ''.join([str(i) for i in sorted(digits, reverse=True)])
        mult3 = [i for i in digits if i % 3==0]
        non3 = [i for i in digits if i % 3!=0]
        non3 = sorted(non3, reverse=True)

        if mod_gap == 1:
            last_odd_idx = [i for i in range(len(non3)) if non3[i] & 1]
            if len(last_odd_idx) > 0:
                last_odd_idx = last_odd_idx[-1]
                non3 = non3[:last_odd_idx] + non3[last_odd_idx+1:]
        elif mod_gap==2:
            last_even_idx =  [i for i in range(len(non3)) if non3[i] % 2==0]
            if len(last_even_idx) > 0:
                last_even_idx = last_even_idx[-1]
                non3 = non3[:last_even_idx] + non3[last_even_idx+1:]
            
        if sum(non3) % 3 != 0:
            non3 = []
        answer = ''.join([str(int(i)) for i in sorted(mult3+non3, reverse=True)])
        
        
        while answer.startswith('0') and len(answer)>1:
            answer = answer[1:] 
        return answer
            


class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        dp = [-1, -1, -1]
        for x in sorted(digits, reverse=True):
            r = x%3
            r1 = 0
            for y in list(dp):
                if y == -1:
                    dp[r] = max(dp[r], x)
                else:
                    dp[(r1+r)%3] = max(dp[(r1+r)%3], 10*y+x)
                r1 += 1
        if dp[0] == -1:
            return ''
        else:
            return str(dp[0])

class Solution:
    def largestMultipleOfThree(self, a: List[int]) -> str:
        n, dp = len(a), [''] * 3
        a.sort(reverse=True)
        for i in range(n):
            d, dp1 = a[i] % 3, [''] * 3
            for j in range(3): 
                k = (j-d) % 3
                dp1[j] = max([dp[k] + str(a[i]) if dp[k] or k==0 else '', dp[j]], key=lambda x: (len(x), x))
                if len(dp1[j]) >= 2 and dp1[j][0] == '0': dp1[j] = dp1[j][1:]
            dp = dp1            
        return dp[0]

class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        digits = collections.Counter(digits)
        final_ans_digits = {i: 0 for i in range(10)}
        for i in range(0, 10, 3):
            final_ans_digits[i] = digits[i]
        
        # append all digits whose quant > 3
        left_numbers = list()
        for i in [1,2,4,5,7,8]:
            if digits[i] > 3:
                undefined = 3 + (digits[i]  % 3)
                left_numbers += [i] * undefined
            else:
                left_numbers += [i] * digits[i]
        
        mod = sum(left_numbers) % 3 
        # but we may need to exclude a couple of numbers
        if not mod:
            pass
        elif not(left_numbers[0] - mod) % 3:
            # have to exclude number, can exclude the smallest
            digits[left_numbers[0]] -= 1
        else:
            # have to exclude some numbers
            # option 1: exclude a single number
            num1 = None
            for n in left_numbers:
                if not (n - mod) % 3:
                    num1 = n
                    digits[n] -= 1
                    break
            if num1 is None:
                # option 2: exclude two numbers
                num2 = None
                for i in range(1, len(left_numbers)):
                    if not (left_numbers[i] + left_numbers[0] - mod) % 3:
                        num2 = left_numbers[i]
                        digits[left_numbers[0]] -= 1
                        digits[num2] -= 1
                if num2 is None:
                    return ''
        
        ans = ''.join(str(i) * digits[i] for i in range(9, -1, -1))
        if not ans:
            return ''
        elif ans[0] == '0':
            return '0'
        
        else:
            return ans
                
                    
            


class Solution:
    def largestMultipleOfThree(self, a: List[int]) -> str:
        n = len(a); a.sort(reverse=True)
        dp = ['']*3
        for i in range(n):
            d = a[i] % 3
            dp1 = ['']*3
            for j in range(3): 
                k = (j-d) % 3
                dp1[j] = max([dp[k] + str(a[i]) if dp[k] or k==0 else '', dp[j]], key=lambda x: (len(x), x))
                if len(dp1[j]) >= 2 and dp1[j][0] == '0': dp1[j] = dp1[j][1:]
            dp = dp1            
        return dp[0] or ''
            


class Solution:
    def largestMultipleOfThree(self, a: List[int]) -> str:
        n = len(a); a.sort(reverse=True)
        dp = ['']*3
        for i in range(n):
            d = a[i] % 3
            dp1 = ['']*3
            for j in range(3): 
                k = (j-d) % 3
                dp1[j] = max([dp[k] + str(a[i]) if dp[k] or k==0 else '', dp[j]], key=lambda x: (len(x), x))
                if len(dp1[j]) >= 2 and dp1[j][0] == '0': dp1[j] = dp1[j][1:]
            dp = dp1            
        return dp[0]
            


class Solution:
    def largestMultipleOfThree(self, a: List[int]) -> str:
        n, dp = len(a), [''] * 3
        a.sort(reverse=True)
        for i in range(n):
            d, dp1 = a[i] % 3, [''] * 3
            for j in range(3): 
                k = (j-d) % 3
                dp1[j] = max([dp[k] + str(a[i]) if dp[k] or k==0 else '', dp[j]], key=lambda x: (len(x), x))
                if len(dp1[j]) >= 2 and dp1[j][0] == '0': dp1[j] = dp1[j][1:]
            dp = dp1            
        return dp[0]
            


import numpy as np
class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        mod_gap = sum(digits) % 3
        if mod_gap == 0:
            answer = ''.join([str(i) for i in sorted(digits, reverse=True)])
        digits = np.array(digits)
        cond = digits % 3 == 0
        mult3 = digits[cond]
        non3 = digits[~cond]
        non3 = sorted(non3, reverse=True)
        non3 = np.array(non3)

        if mod_gap == 1:
            last_odd_idx = np.ravel(np.argwhere(non3 & 1))
            if len(last_odd_idx) > 0:
                last_odd_idx = last_odd_idx[-1]
                non3 = list(non3[:last_odd_idx]) + list(non3[last_odd_idx+1:])
        elif mod_gap==2:
            last_even_idx = np.ravel(np.argwhere(non3 % 2==0))
            if len(last_even_idx) > 0:
                last_even_idx = last_even_idx[-1]
                non3 = list(non3[:last_even_idx]) + list(non3[last_even_idx+1:])
            
        if sum(non3) % 3 != 0:
            non3 = []
        answer = ''.join([str(int(i)) for i in sorted (np.concatenate([mult3, non3]), reverse=True)])
        
        
        while answer.startswith('0') and len(answer)>1:
            answer = answer[1:] 
        return answer
            


class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        digits.sort(reverse=True)
        N = len(digits)
        dp = [[float('-inf')] * N for _ in range(3)]
        for n in range(N):
            for k in [0, 1, 2, 0]:
                if n == 0 or (dp[k][n-1] == float('-inf') and dp[(k - digits[n]) % 3][n-1] == float('-inf')):
                    if digits[n] % 3 == k:
                        dp[k][n] = digits[n]
                else:
                    if digits[n] % 3 == 0:
                        dp[k][n] = dp[k][n-1] * 10 + digits[n]
                    else:
                        dp[k][n] = max(dp[k][n-1], dp[(k - digits[n]) % 3][n-1] * 10 + digits[n])

        return str(dp[0][-1]) if dp[0][-1] != float('-inf') else ''

class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        state2nums = defaultdict(Counter)
        digits.sort(reverse=True)
        for num in digits:
            delta = num % 3
            nstate = defaultdict(Counter)
            
            for i in range(3):
                if sum(v for k, v in list(state2nums[i].items())) == 0 and i != 0:
                    continue
                target = (delta+i) % 3
                
                if sum(v for k, v in list(state2nums[target].items())) < sum(v for k, v in list(state2nums[i].items()))+1:
                    counter = Counter(state2nums[i])
                    counter[num] += 1
                    nstate[target] = counter
            
            for i in range(3):
                if i in nstate:
                    state2nums[i] = nstate[i]
            # print(state2nums)
        print(state2nums)
        nums = sorted([k for k, v in list(state2nums[0].items()) for _ in range(v) ], reverse=True)
        ret = ''.join(map(str, nums))
        return '0' if ret and ret[0] == '0' else ret


class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        n = len(digits)
        
        f = [0] * 10
        for x in digits:
            f[x] += 1
            
        M = defaultdict(int)
        
        def upper(d, m): # largest 3k + m: 3k + m <= f[d]
            if f[d] < m:
                return 0
            return (f[d]-m)//3*3+m
        
        def mx(d, mod): # largest k: 0 <= k <= f[d] && k * d % 3 = mod
            dm = d % 3  
            if dm == 0:
                return 0 if mod != 0 else f[d]
            if dm == 1:
                return upper(d, mod)
            if dm == 2:
                return upper(d, (3 - mod) % 3)
                
        for i in range(10):
            for j in range(3):
                M[i, j] = mx(i, j)
        
        X = [0] * 10
        R = [0] * 10
        def findout(i, mod):
            if i < 0:
                if mod == 0:
                    gt = False
                    sx = sr = 0
                    for i in range(10):
                        sx += X[i]
                        sr += R[i]
                    if sx > sr:
                        gt = True
                    elif sx == sr:
                        for i in reversed(list(range(10))):
                            if X[i] > R[i]:
                                gt = True
                                break
                            elif X[i] < R[i]:
                                break
                    if gt:
                        for i in range(10):
                            R[i] = X[i]
                return
            for j in range(3):
                if M[i, j] > 0:
                    X[i] = M[i, j]
                    findout(i-1, (mod + j) % 3)
                    X[i] = 0
            findout(i-1, mod)            
        
                
        findout(9, 0)
        ret = ''
        
        for i in reversed(list(range(10))):
            if R[i] > 0:
                ret += R[i] * str(i)
                
        if len(ret) > 0 and ret[0] == '0':
            ret = '0'
            
        return ret
                
                
        
        


class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        dp = [-1, -1, -1]
        for x in sorted(digits)[::-1]:
            for a in dp[:] + [0]:
                y = a * 10 + x
                dp[y % 3] = max(dp[y % 3], y)
        return str(dp[0]) if dp[0] >= 0 else ''


class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        vals = {0 : 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
        total = 0
        res = []
        for digit in digits:
            vals[digit] += 1
            total += int(digit)
        if total % 3 == 0:
            temp = 0
            for i in range(9,0,-1):
                temp += vals[i]
            if temp == 0:
                return '0'
            for i in range(9,-1,-1):
                for _ in range(vals[i]):
                    res.append(str(i))
            return ''.join(res)
        
        if total % 3 == 1:
            for i in range(10):
                if i%3 == 1 and vals[i] > 0:
                    vals[i] -= 1
                    for i in range(9,-1,-1):
                        for _ in range(vals[i]):
                            res.append(str(i))
                    return ''.join(res)
            count = 0
            i = 0
            while i < 10:
                if count == 2:
                    for i in range(9,-1,-1):
                        for _ in range(vals[i]):
                            res.append(str(i))
                    return ''.join(res)
                elif i%3 == 2 and vals[i] > 0:
                    vals[i] -= 1
                    count += 1
                else:
                    i += 1
        else:
            for i in range(10):
                if i%3 == 2 and vals[i] > 0:
                    vals[i] -= 1
                    for i in range(9,-1,-1):
                        for _ in range(vals[i]):
                            res.append(str(i))
                    return ''.join(res)
            count = 0
            i = 0
            while i < 10:
                if count == 2:
                    for i in range(9,-1,-1):
                        for _ in range(vals[i]):
                            res.append(str(i))
                    return ''.join(res)
                elif i%3 == 1 and vals[i] > 0:
                    vals[i] -= 1
                    count += 1
                else:
                    i += 1
                    
                        
                    
        return ''.join(res)


class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        r_to_nums = {i:list() for i in range(3)}
        for x in digits:
            r = x % 3
            r_to_nums[r].append(x)
            
        for i in range(3):
            r_to_nums[i].sort()

        counter = collections.Counter()
        for x in digits:
            counter[str(x)] += 1

        r = sum(digits)%3
        if r == 1:
            if r_to_nums[1]:
                y = str(r_to_nums[1][0])
                counter[y] -= 1
            elif len(r_to_nums[2]) >= 2:
                y = str(r_to_nums[2][0])
                counter[y] -= 1
                y = str(r_to_nums[2][1])
                counter[y] -= 1
            else:
                return ''
        elif r == 2:
            if r_to_nums[2]:
                y = str(r_to_nums[2][0])
                counter[y] -= 1
            elif len(r_to_nums[1]) >= 2:
                y = str(r_to_nums[1][0])
                counter[y] -= 1
                y = str(r_to_nums[1][1])
                counter[y] -= 1
            else:
                return ''
        
        res = ''
        for x in sorted(counter, reverse=True):
            cnt = counter[x]
            res += x*cnt
        if not res:
            return res
        return str(int(res))


class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        dic=defaultdict(list)
        for d in digits:dic[d%3].append(d)
        arr=[]
        n1=len(dic[1])
        n2=len(dic[2])
        arr+=dic[0]
        if n1%3==n2%3==0 or n1==n2:arr+=dic[1]+dic[2]
        else:
            dic[1].sort(reverse=1)
            dic[2].sort(reverse=1)
            l1=l2=0
            if n1%3==2 and n2==3:
                while n2>3:
                    l2+=3
                    n2-=3
                l1+=n1//3*3
                l1+=2
                l2+=2
            elif n2%3==2 and n1==3:
                while n1>3:
                    l1+=3
                    n1-=3
                l2+=n2//3*3
                l2+=2
                l1+=2
            else:
                if n1>2:
                    l1+=n1//3*3
                    n1-=n1//3*3
                if n2>2:
                    l2+=n2//3*3
                    n2-=n2//3*3
                if n1!=0 and n2!=0:
                    min1=min(n1,n2)
                    l1+=min1
                    l2+=min1
            arr+=dic[1][:l1]+dic[2][:l2]
        arr.sort(reverse=1)
        if arr and arr[0]==0:return '0'
        return ''.join(str(i) for i in arr)