Given two binary strings and , return their sum as a binary string. For example, if and , return .
You cannot convert to integers and add, because the inputs can be very long (up to characters). You must perform binary addition manually, digit by digit, handling carries.
This is like adding two numbers on paper: start from the right, add digits and carry over when the sum exceeds the base. Before reading on, think about how to track the carry and build the result.