class Solution {
public:
string largestMultipleOfThree(vector<int>& digits) {
vector<int> counter = vector<int>(10, 0);
int total = 0;
for (const int& d : digits) {
counter[d]++;
total += d;
}
if (total % 3 == 0) return getResult(counter);
else if (total % 3 == 1) {
if (tryRemove(counter, 1, 1)) return getResult(counter);
if (tryRemove(counter, 4, 1)) return getResult(counter);
if (tryRemove(counter, 7, 1)) return getResult(counter);
if (tryRemove(counter, 2, 2)) return getResult(counter);
if (tryRemove(counter, 5, 2)) return getResult(counter);
if (tryRemove(counter, 8, 2)) return getResult(counter);
} else if (total % 3 == 2) {
if (tryRemove(counter, 2, 1)) return getResult(counter);
if (tryRemove(counter, 5, 1)) return getResult(counter);
if (tryRemove(counter, 8, 1)) return getResult(counter);
if (tryRemove(counter, 1, 2)) return getResult(counter);
if (tryRemove(counter, 4, 2)) return getResult(counter);
if (tryRemove(counter, 7, 2)) return getResult(counter);
}
return "";
}
bool tryRemove(vector<int>& counter, int num, int size) {
if (counter[num] >= size) {
counter[num] -= size;
return true;
} else {
return false;
}
}
string getResult(vector<int>& counter) {
string res = "";
for (int i = 9; i >= 0; i--) {
while (counter[i] != 0) {
res += '0' + i;
counter[i]--;
}
}
return res.length() > 1 && res[0] == '0' ? "0" : res;
}
};