<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 transform(counter: "Counter") -> str:
            num = ""
            for i in range(9, -1, -1):
                num += str(i) * counter[i]
            return num

        def max_string(num1: str, num2: str) -> str:
            if len(num1) < len(num2):
                return num2
            elif len(num1) > len(num2):
                return num1

            for d1, d2 in zip(num1, num2):
                if d1 > d2:
                    return num1
                elif d2 > d1:
                    return num2
            return num1
        
        total = sum(digits)
        res = ""
        counter = Counter(digits)
        reminders = {
            1: [1, 4, 7],
            2: [2, 5, 8]
        }
        if total % 3 != 0:
            for i in reminders[total % 3]:
                if counter[i] > 0:
                    counter[i] -= 1
                    res = max_string(res, transform(counter))
                    counter[i] += 1
                    break
            for i in reminders[3 - total % 3]:
                if counter[i] > 0:
                    counter[i] -= 1
                    for j in reminders[3 - total % 3]:
                        if counter[j] > 0:
                            counter[j] -= 1
                            res = max_string(res, transform(counter))
                            counter[j] += 1
                    counter[i] += 1
        else:
            res = max_string(res, transform(counter))
        if res != "" and res.count("0") == len(res):
            res = "0"
        return res

129