Add Binary Strings

Given two binary strings s1 and s2 consisting of only 0s and 1s. Find the resultant string after adding the two Binary Strings.
Note: The input strings may contain leading zeros but the output string should not have any leading zeros.

Input: s1 = "1101", s2 = "111"
Output: 10100
Explanation:
 1101
+ 111
10100

Input: s1 = "00100", s2 = "010"
Output: 110
Explanation: 
  100
+  10
 110

Constraints:
1 ≤s1.size(), s2.size()≤ 10⁶

Approach 01:

#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    string addBinary(string& binary_str1, string& binary_str2) {
        // Equalize lengths by adding leading zeros
        int max_len = max(binary_str1.size(), binary_str2.size());
        binary_str1 = string(max_len - binary_str1.size(), '0') + binary_str1;
        binary_str2 = string(max_len - binary_str2.size(), '0') + binary_str2;

        // Binary addition mapping
        unordered_map<string, string> binary_mapping = {
            {"000", "00"}, {"001", "01"}, {"010", "01"}, {"011", "10"},
            {"100", "01"}, {"101", "10"}, {"110", "10"}, {"111", "11"}
        };

        string result = "";
        char carry = '0';

        // Perform binary addition from the least significant digit
        for (int i = max_len - 1; i >= 0; --i) {
            string current_sum = string(1, carry) + binary_str1[i] + binary_str2[i];
            result = binary_mapping[current_sum][1] + result;
            carry = binary_mapping[current_sum][0];
        }

        // Handle any remaining carry
        if (carry == '1') {
            result = '1' + result;
        }

        // Remove leading zeros
        result.erase(0, result.find_first_not_of('0'));
        return result.empty() ? "0" : result;
    }
};

class Solution:
    def addBinary(self, binary_str1: str, binary_str2: str) -> str:
        # Equalize lengths by adding leading zeros
        max_len = max(len(binary_str1), len(binary_str2))
        binary_str1 = binary_str1.zfill(max_len)
        binary_str2 = binary_str2.zfill(max_len)
        
        # Binary addition mapping
        binary_mapping = {
            '000': '00', '001': '01', '010': '01', '011': '10',
            '100': '01', '101': '10', '110': '10', '111': '11'
        }
        
        result = ''
        carry = '0'
        
        # Perform binary addition from the least significant digit
        for i in range(1, max_len + 1):
            digit1 = binary_str1[-i]
            digit2 = binary_str2[-i]
            current_sum = carry + digit1 + digit2
            result = binary_mapping[current_sum][1] + result
            carry = binary_mapping[current_sum][0]
        
        # Handle any remaining carry
        if carry == '1':
            result = '1' + result
        
        # Remove leading zeros
        result = result.lstrip('0')
        return result if result else '0'

Time Complexity

• Equalizing lengths:

  To equalize the lengths of the two binary strings, leading zeros are added. This involves constructing two new strings of size \(O(\max(n, m))\), where \(n\) and \(m\) are the lengths of the input strings. The operation takes \(O(\max(n, m))\).

• Binary addition:

  The binary addition loop iterates over the length of the strings, which is \(O(\max(n, m))\). For each character, a constant amount of work is done for the lookup in the binary mapping and string concatenation.

• Removing leading zeros:

  Removing leading zeros involves traversing the result string once, which takes \(O(\max(n, m))\).

• Overall Time Complexity:

  The overall time complexity is \(O(\max(n, m))\), where \(n\) and \(m\) are the lengths of the two input binary strings.

Space Complexity

• Auxiliary Space:

  The main space usage comes from the result string, which requires \(O(\max(n, m))\) space to store the final binary sum. The additional space for the mapping is constant \(O(1)\) because it does not grow with the input size.

• Modified Input Strings:

  The input strings binary_str1 and binary_str2 are padded to equal length, consuming \(O(\max(n, m))\) space.

• Overall Space Complexity:

  The overall space complexity is \(O(\max(n, m))\), dominated by the result string and the padded input strings.