<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 trim(string s){
        int i = 0;
        while(i<s.length() && s[i] == '0') i+=1;
        return s.substr(i);
    }

    string largestMultipleOfThree(vector<int>& digits) {
        int sum = 0;
        string ans ="";
        bool zero = false;
        for(auto it: digits){
            sum += (it);
            if(it == 0) zero = true;
            ans += char(it+'0');
        }
        sort(ans.rbegin(), ans.rend());
        if(sum % 3 == 0){
            string cp = trim(ans);
            if(cp == "" && zero) return "0";
            else return cp;
        }
        
        if(sum%3 == 1){
            // remove one element with x%3 == 1
            // or remove two element with x%3 == 2
            int ind = -1;
            for(int i = ans.size()-1; i>=0; i--){
                if((ans[i]-'0')%3 == 1){
                    ind = i;
                    break;
                }
            }

            if(ind != -1){
                ans.erase(ind,1);
                string cp = trim(ans);
            if(cp == "" && zero) return "0";
            else return cp;
            }else{
                int first = -1;
                int second = -1;
                for(int i = ans.size()-1; i>=0; i--){
                    if((ans[i]-'0')%3 == 2){
                        if(first == -1) first = i;
                        else if(second == -1) second = i;
                    }
                }
                if(first == -1 || second == -1) return "";
                ans.erase(first,1);
                ans.erase(second,1);
               string cp = trim(ans);
            if(cp == "" && zero) return "0";
            else return cp;
            }

        }else if(sum %3 == 2){
             int ind = -1;
            for(int i = ans.size()-1; i>=0; i--){
                if((ans[i]-'0')%3 == 2){
                    ind = i;
                    break;
                }
            }

            if(ind != -1){
                ans.erase(ind,1);
                string cp = trim(ans);
            if(cp == "" && zero) return "0";
            else return cp;
            }else{
                int first = -1;
                int second = -1;
                for(int i = ans.size()-1; i>=0; i--){
                    if((ans[i]-'0')%3 == 1){
                        if(first == -1) first = i;
                        else if(second == -1) second = i;
                    }
                }
                if(first == -1 || second == -1) return "";
                ans.erase(first,1);
                ans.erase(second,1);
                string cp = trim(ans);
            if(cp == "" && zero) return "0";
            else return cp;
            }

        }
        
        return "";
        
    }
};
25300