Given two binary strings, return their sum (also a binary string).

Example:

```a = "100"

b = "11"
```
Return a + b = “111”.

Solution:

Time: O(m + n)
Space: O(m + n)

```public class Solution {
public String addBinary(String A, String B) {
StringBuilder sb = new StringBuilder();
int i = A.length() - 1;
int j = B.length() - 1;
int carry = 0;
while (i >= 0 && j >= 0) {
int a = A.charAt(i) - '0';
int b = B.charAt(j) - '0';
int d = (a + b + carry) % 2;
carry = (a + b + carry) >= 2 ? 1 : 0;
sb.append(String.valueOf(d));
i --;
j --;
}
while (i >= 0) {
int a = A.charAt(i) - '0';
int d = (a + carry) % 2;
carry = (a + carry) >= 2 ? 1 : 0;
sb.append(String.valueOf(d));
i --;
}
while (j >= 0) {
int b = B.charAt(j) - '0';
int d = (b + carry) % 2;
carry = (b + carry) >= 2 ? 1 : 0;
sb.append(String.valueOf(d));
j --;
}
if (carry == 1) {
sb.append('1');
}
return sb.reverse().toString();
}
}```

```class Solution {
public String addBinary(String a, String b) {
StringBuilder sb = new StringBuilder();
int i = a.length() - 1;
int j = b.length() - 1;
int carry = 0;
while (i >= 0 && j >= 0) {
int aVal = a.charAt(i) - '0';
int bVal = b.charAt(j) - '0';
int val = (aVal + bVal + carry) % 2;
carry = (aVal + bVal + carry) / 2;
sb.append(val + "");
i --;
j --;
}
while (i >= 0) {
int aVal = a.charAt(i) - '0';
int val = (aVal + carry) % 2;
carry = (aVal + carry) / 2;
sb.append(val + "");
i --;
}
while (j >= 0) {
int bVal = b.charAt(j) - '0';
int val = (bVal + carry) % 2;
carry = (bVal + carry) / 2;
sb.append(val + "");
j --;
}
if (carry > 0) {
sb.append(carry);
}
return sb.reverse().toString();
}
}```