<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>

/*
walk through the strings from right to left and construct a new string

what are the cases?

a b c r nc
0 0 1 1 0
1 0 1 0 1
1 1 1 1 1
0 0 0 0 0
0 1 0 1 0
1 0 0 1 0
1 1 0 0 1

*/

class Solution {
public:

    char giveMeNextChar(char a, char b, bool& carry){
        if (carry){
            if (a == '0' && b == '0'){
                carry = false;
                return '1';
            }
            if (a == '1' && b == '1'){
                carry = true;
                return '1';
            }
            carry = true;
            return '0';
        }else{
            if (a == '0' && b == '0'){
                carry = false;
                return '0';
            }
            if (a == '1' && b == '1'){
                carry = true;
                return '0';
            }
            carry = false;
            return '1';
        }
    }

    string addBinary(string a, string b) {
        int la = a.size();
        int lb = b.size();

        int shorter = min(la, lb);

        string res = "";
        bool carry = false;
        int i = 0;
        
        while ( i < la || i < lb){
            char ca = (i < la) ? a[la-i-1] : '0';
            char cb = (i < lb) ? b[lb-i-1] : '0';

            res = giveMeNextChar(ca,cb,carry) +res;
            i++;
        }

        if (carry){
            res = '1'+res;
        }

        return res;
    }
};
11000