<p>Given an array of digits <code>digits</code>, return <em>the largest multiple of <strong>three</strong> that can be formed by concatenating some of the given digits in <strong>any order</strong></em>. If there is no answer return an empty string.</p>

<p>Since the answer may not fit in an integer data type, return the answer as a string. Note that the returning answer must not contain unnecessary leading zeros.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> digits = [8,1,9]
<strong>Output:</strong> &quot;981&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> digits = [8,6,7,1,0]
<strong>Output:</strong> &quot;8760&quot;
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> digits = [1]
<strong>Output:</strong> &quot;&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= digits.length &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= digits[i] &lt;= 9</code></li>
</ul>

class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        d = [[],[],[]]
        for dig in digits:
            d[dig%3].append(dig)
        print(d)
        #remainders
        n1 = len(d[1])
        n2=len(d[2])
        #pairs
        p1=int(n1/2)
        p2=int(n2/2)
        dp=min(p1,p2)
        #remove possible double pairs
        r1=n1-2*dp
        r2=n2-2*dp
        #remove triplets
        r1%=3
        r2%=3
        #check cross pairs and remove min left overs
        if r1==r2:
            pass
        else:
            if r1==0:
                if r2==1:
                    removeSmallest(d[2])
                elif r2==2:
                    if n1>0:
                        removeSmallest(d[1])
                    else:
                        removeSmallest(d[2],2)
            elif r1==1:
                if r2==0:
                    removeSmallest(d[1],1)
                elif r2==2:
                    removeSmallest(d[2],1)
            elif r1==2:
                if r2==0:
                    if n2>0:
                        removeSmallest(d[2])
                    else:
                        removeSmallest(d[1],2)
                elif r2==1:
                    removeSmallest(d[1])
        ans = "".join([str(x) for x in sorted(d[0]+d[1]+d[2],reverse=True)])
        if len(ans)>0 and ans[0]=="0":
            return "0"
        return ans
        
def removeSmallest(arr,c=1):
    if c<=0:
        return
    smallest = 0
    for i in range(1,len(arr)):
        if arr[i]<arr[smallest]:
            smallest=i
    arr.pop(smallest)
    removeSmallest(arr,c-1)
141