<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 {
public:
    string largestMultipleOfThree(vector<int>& digits) {
        vector<int> mod1, mod2;
        multiset<int> res;
        int sum = 0;
        for(auto digit: digits){
            if(digit%3 == 1){
                mod1.push_back(digit);
            }
            else if(digit%3 == 2){
                mod2.push_back(digit);
            } 
            res.insert(digit);
            sum += digit;
        }
        int rem = sum%3;

        sort(mod1.begin(), mod1.end());
        sort(mod2.begin(), mod2.end());

        if(rem == 1){
            if(mod1.size() >= 1){
                res.erase(res.find(mod1[0]));
            }
            else{
                res.erase(res.find(mod2[0]));
                res.erase(res.find(mod2[1]));
            }
        }
        else if(rem == 2){
            if(mod2.size() >= 1){
                res.erase(res.find(mod2[0]));
            }
            else{
                res.erase(res.find(mod1[0]));
                res.erase(res.find(mod1[1]));
            }
        }

        string ans = "";
        for(auto digit : res){
            ans.push_back(digit + '0');
        }
        reverse(ans.begin(), ans.end());
        if(ans[0] == '0'){
            return "0";
        }
        return ans;
    }
};
32500