1. Understanding the Problem

You are given two binary strings a and b. Your task is to return their sum, also represented as a binary string.

For example, if a = "11" and b = "1", your function should return "100".

The Core Constraint (The Trap):

Most modern languages have built-in functions to easily parse strings into base-10 integers, add them, and convert them back to binary (e.g., bin(int(a, 2) + int(b, 2)) in Python). Do not do this in an interview. The hidden trap is that these binary strings can be massive (up to 10,000 characters long). Converting a 10,000-bit binary string into an integer will cause a catastrophic integer overflow in statically typed languages like Java or C++, crashing your program.

2. The Naive Approach: Type Conversion

The most intuitive way to solve this is to let the programming language do the heavy lifting: parse the strings into native integer types, add them using the standard + operator, and format the output back to a binary string.

Trade-off Analysis

While this logic works for small inputs, it completely defeats the purpose of the algorithmic challenge:

• Time Complexity: O(N + M) — It takes linear time to parse the strings.
• Space Complexity: O(N + M) — It takes linear space to store the new strings.
• The Fatal Flaw: If the string length exceeds 64 bits, standard long variables will overflow. You would be forced to use heavy BigInteger libraries, which interviewers usually forbid for this specific problem.

3. The Optimal Approach: Bit-by-Bit Addition (Grade-School Math)

To pass a senior-level technical interview, we must perform the addition manually, exactly like you learned in elementary school. We align the two numbers on top of each other, start from the rightmost column (the least significant bit), add the digits, and carry over any excess to the next column.

Imagine you are a cashier physically counting pennies, dimes, and dollars. When you have ten pennies, you don't write down "10" in the penny column; you write "0" and carry a "1" over to the dimes column. Binary works the exact same way, but the threshold is 2 instead of 10. If a column sums to 2 (e.g., 1 + 1), you write 0 and carry over a 1.

By processing the numbers character by character, our strings can be infinitely long without ever causing an integer overflow!

4. The Logic Step-by-Step

1. Initialize Trackers:
   • Set two pointers, i and j, pointing to the last characters (rightmost ends) of strings a and b respectively.
   • Initialize a carry variable to 0.
   • Initialize an empty structure (like a list or StringBuilder) to build your result.
2. Traverse Backwards: Create a loop that continues as long as i >= 0 OR j >= 0 OR carry > 0.
   • Initialize a total for the current column, starting with the value of carry.
   • If i >= 0, add the integer value of a[i] to total, and decrement i.
   • If j >= 0, add the integer value of b[j] to total, and decrement j.
   • The Math: Append total % 2 (the remainder) to your result. Update carry to total / 2 (the quotient).
3. When the loop finishes, your result structure has the answer built backwards. Reverse the structure, convert it to a string, and return it.

5. Complexity Analysis

• Time Complexity: O(max(N, M)) — We iterate through both strings completely. The time taken is proportional to the length of the longer string.
• Space Complexity: O(max(N, M)) — We need to store the resulting string, which will be at most 1 character longer than the longest input string (due to a final carry).

6. Code Implementations

Expand the sections below to see the optimal "Grade-School Math" implementations across different languages.

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        res = []
        i = len(a) - 1
        j = len(b) - 1
        carry = 0
        
        # Continue if there are characters left or a carry left over
        while i >= 0 or j >= 0 or carry:
            total = carry
            
            if i >= 0:
                total += int(a[i])
                i -= 1
                
            if j >= 0:
                total += int(b[j])
                j -= 1
                
            # append the remainder to our result
            res.append(str(total % 2))
            # update carry
            carry = total // 2
            
        # Reverse the array and join into a string
        return "".join(res[::-1])

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder res = new StringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        
        while (i >= 0 || j >= 0 || carry > 0) {
            int total = carry;
            
            if (i >= 0) {
                // Convert char to int by subtracting ASCII '0'
                total += a.charAt(i) - '0';
                i--;
            }
            
            if (j >= 0) {
                total += b.charAt(j) - '0';
                j--;
            }
            
            res.append(total % 2);
            carry = total / 2;
        }
        
        // The result was built backwards, so reverse it
        return res.reverse().toString();
    }
}

#include <string>
#include <algorithm>

class Solution {
public:
    std::string addBinary(std::string a, std::string b) {
        std::string res = "";
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        
        while (i >= 0 || j >= 0 || carry > 0) {
            int total = carry;
            
            if (i >= 0) {
                total += a[i] - '0';
                i--;
            }
            
            if (j >= 0) {
                total += b[j] - '0';
                j--;
            }
            
            res += std::to_string(total % 2);
            carry = total / 2;
        }
        
        // Reverse the accumulated string
        std::reverse(res.begin(), res.end());
        
        return res;
    }
};

7. Conclusion: You Are Ready

Congratulations, you have successfully implemented a string-based hardware simulator! Understanding how to bypass language-specific integer limits by reverting to foundational math algorithms is a hallmark of a robust software engineer. This bit-by-bit manipulation pattern is incredibly versatile. Keep this "pointer and carry" mental model sharp, as you will use this exact same architecture to solve related interview classics like Add Two Numbers (using Linked Lists) and Multiply Strings!