A hardware simulator stores register values as strings of 0 and 1. Given two such strings x and y (non-empty, no leading zeros except "0" itself), return their sum as a binary string, computed column by column without converting the whole strings to integers.
Examples
Input: x = "1011", y = "11"
Output: "1110"
Explanation: 11 + 3 = 14.
Input: x = "0", y = "0"
Output: "0"
Constraints
1 <= len(x), len(y) <= 5000- Target: O(len(x) + len(y)) time.
Goals
- Walk two strings from their right ends with independent indices
- Carry a single bit between columns
- Build the answer backwards and reverse it once