1980. Find Unique Binary String

Problem Description

Given an array of unique binary strings nums, each of length n, find and return a binary string of length n that does not appear in nums. If multiple solutions exist, return any one.

Solution: Bit Manipulation and Enumeration

This solution leverages bit manipulation to efficiently find a missing binary string. The core idea is that the number of 1s in a binary string of length n can range from 0 to n. We can use a bitmask to track which counts of 1s are already present in the input strings. Then, we iterate through possible counts of 1s, and the first count not present in the bitmask corresponds to a missing binary string.

Algorithm:

1. Create a bitmask: Initialize an integer mask to 0. Iterate through each string in nums. Count the number of 1s in the string. Set the corresponding bit in mask to 1 using a left bit shift (1 << count).

2. Find a missing count: Iterate from 0 to n (inclusive). For each count i, check if the i-th bit in mask is 0 (using a bitwise AND operation: mask >> i & 1). If it's 0, it means a string with i ones is missing.

3. Construct and return the string: Create a string with i ones followed by n - i zeros. This string is guaranteed to be unique and not present in nums.

Time Complexity: O(n^2), where n is the length of the input strings and the number of strings. The nested loops in the Java solution contribute to this complexity. However, it can be considered O(L) where L is the total number of characters in all input strings. The bit manipulation operations themselves are O(1).

Space Complexity: O(1). The space used is constant regardless of input size.

Code Implementation (Python)

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        mask = 0
        for x in nums:
            mask |= 1 << x.count("1")  #Set bit corresponding to count of 1s
        n = len(nums)
        for i in range(n + 1):
            if (mask >> i) & 1 == 0: #Check if bit is 0 (string with i ones is missing)
                return "1" * i + "0" * (n - i)

Code Implementation (Java)

class Solution {
    public String findDifferentBinaryString(String[] nums) {
        int mask = 0;
        for (String x : nums) {
            int cnt = 0;
            for (char c : x.toCharArray()) {
                if (c == '1') cnt++;
            }
            mask |= 1 << cnt;
        }
        for (int i = 0; i <= nums.length; i++) {
            if ((mask >> i) & 1 == 0) {
                return "1".repeat(i) + "0".repeat(nums.length - i);
            }
        }
        return ""; //Should not reach here given the problem constraints
    }
}

Other Languages: The implementations in C++, Go, TypeScript, and C# follow a similar structure, adapting the syntax and libraries as needed. The core algorithm remains consistent across all languages.