<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:
        def build(take):
            ans=""
            status=0
            for d in range(9,-1,-1):
                if take[d]>0:
                    status |= 1
                    if d>0:
                        status |= 2
                
                ans += str(d)*take[d]
            if not status:
                return ""
            if not status&2:
                return "0"
            return ans
        
        cnt=[0]*10

        for d in digits:
            cnt[d] += 1

        rem0=[0,3,6,9]
        rem1=[1,4,7]
        rem2=[2,5,8]
        sm1=sum(cnt[d] for d in rem1)
        sm2=sum(cnt[d] for d in rem2)
        tot=(sm1+2*sm2)%3
        if tot==0:
            return build(cnt)
        if tot==1:
            if sm1>0:
                for d in rem1:
                    if cnt[d]>0:
                        cnt[d] -= 1
                        return build(cnt)
            elif sm2>=2:
                seen=0
                for d in rem2:
                    if cnt[d]==1:
                        seen += 1
                        cnt[d] = 0
                    elif cnt[d]>1:
                        cnt[d] -= (2-seen)
                        seen = 2
                    if seen>=2:
                        return build(cnt)
            else:
                for d in rem2:
                    cnt[d] %= 3
                return build(cnt)
        if tot==2:
            if sm2>0:
                for d in rem2:
                    if cnt[d]>0:
                        cnt[d] -= 1
                        return build(cnt)
            elif sm1>=2:
                seen=0
                for d in rem1:
                    if cnt[d]==1:
                        seen += 1
                        cnt[d] = 0
                    elif cnt[d]>1:
                        cnt[d] -= (2-seen)
                        seen = 2
                    if seen>=2:
                        return build(cnt)
            else:
                for d in rem1:
                    cnt[d] %= 3
                return build(cnt)
                
114