Add Binary

Add Binary

Given two binary strings a and b, return their sum as a binary string.

Examples

Example 1:

Input: a = "11", b = "1"
Output: "100"
Explanation:
  11
+  1
---
 100

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"
Explanation:
  1010
+ 1011
-----
 10101

Example 3:

Input: a = "0", b = "0"
Output: "0"

Constraints

• 1 <= a.length, b.length <= 10^4
• a and b consist only of '0' or '1' characters.
• Each string does not contain leading zeros except for the zero itself.

Expected Complexity

• Time: O(max(m, n)) where m and n are the lengths of the input strings
• Space: O(max(m, n)) for the result string