1980. Find Unique Binary String

The candidate described two approaches to solve the problem of finding a unique binary string:

Approach 1: Cantor's Diagonalization

1. Construct a string where each bit is different from nums[i][i].
2. This guarantees the new string is not in nums (since it differs in at least one position from each string).

Python Implementation:

class Solution(object):
    def findDifferentBinaryString(self, nums):
        """
        :type nums: List[str]
        :rtype: str
        """
        return "".join("1" if nums[i][i] == "0" else "0" for i in range(len(nums)))

Complexity Analysis:

• Time Complexity: O(n) → One pass to construct the string.
• Space Complexity: O(n) → Output string storage.

Approach 2: Brute Force (Checking All Possible Strings)

1. Generate all n-bit binary strings.
2. Check if any is missing in nums.
3. Return the first missing string.

Python Implementation:

class Solution(object):
    def findDifferentBinaryString(self, nums):
        """
        :type nums: List[str]
        :rtype: str
        """
        seen = set(nums)
        n = len(nums)

        for i in range(2 ** n):  # Generate all possible binary strings of length n
            binary_str = bin(i)[2:].zfill(n)
            if binary_str not in seen:
                return binary_str

Complexity Analysis:

• Time Complexity: O(2^n * n) → Generating and checking all strings.
• Space Complexity: O(2^n) → Worst case storing all possible strings.

No feedback provided.