Add two binary strings
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given two binary strings `a` and `b` (each consisting only of characters `'0'` and `'1'`). Return their sum as a binary string.
## Input
- `a`: string, length `1..10^5`
- `b`: string, length `1..10^5`
## Output
- A string representing `a + b` in base-2, with no leading zeros unless the result is exactly `"0"`.
## Constraints / Notes
- You may not convert the entire strings to built-in integers (they may exceed 64-bit limits).
- Time: `O(|a| + |b|)`; extra space should be `O(|a| + |b|)` (or better).
## Example
- `a = "1011"`, `b = "110"` → output: `"10001"`
Quick Answer: This question evaluates proficiency with binary arithmetic and string manipulation, focusing on carry propagation and handling of very long inputs without relying on native integer conversion.
Return the binary-string sum of a and b without converting the full strings to integers.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ('1011','110')
Expected Output: '10001'
Explanation: 11 + 6 = 17.
Input: ('0','0')
Expected Output: '0'
Explanation: Zero plus zero is zero.
Input: ('1111','1')
Expected Output: '10000'
Explanation: Carry propagates across all digits.
Hints
- Clarify edge cases before coding.
- Keep outputs deterministic when several valid answers exist.