<p>Given two binary strings <code>a</code> and <code>b</code>, return <em>their sum as a binary string</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> a = "11", b = "1"
<strong>Output:</strong> "100"
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> a = "1010", b = "1011"
<strong>Output:</strong> "10101"
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= a.length, b.length &lt;= 10<sup>4</sup></code></li>
	<li><code>a</code> and <code>b</code> consist&nbsp;only of <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code> characters.</li>
	<li>Each string does not contain leading zeros except for the zero itself.</li>
</ul>

class Solution {
public:
    string addBinary(string a, string b) {
        bool carry = false;
        string result;
        string sub;        
        string ans;

        while (a.size() != 0 && b.size() != 0) {
            if (carry) result = binSum("1" + string(1, a.back()) + string(1, b.back()));
            else result = binSum(string(1, a.back()) + string(1, b.back()));

            if (result.size() == 1) carry = false;
            else carry = true;

            a.pop_back();
            b.pop_back();

            ans.insert(ans.begin(), result.back());
        }

        if (carry && a.size() == 0 && b.size() == 0) {ans.insert(ans.begin(), '1'); return ans;}
        else if (!carry && a.size() == 0 && b.size() == 0) return ans;
        else sub = (a.size() > b.size()) ? a : b;

        while (sub.size() > 0) {
            if (carry) result = binSum("1" + string(1, sub.back()));
            else break;            

            if (result.size() == 1) carry = false;
            else carry = true;

            sub.pop_back();

            ans.insert(ans.begin(), result.back());
        }

        if (carry && sub.size() == 0) ans.insert(ans.begin(), '1');
        else if (sub.size() != 0) ans = sub + ans;
        
        return ans;
    }

    string binSum(string backs) {
        if (backs.size() == 3) {
            if (backs == "101" || backs == "110") return "10";
            else if (backs == "100") return "1";
            else return "11";
        } else {
            if (backs == "10" || backs == "01") return "1";
            else if (backs == "00") return "0";
            else return "10";
        }
    }

    // WTF AM I WRITING??
};
9400