1980. Find Unique Binary String - Detailed Explanation

Problem Statement

Description:
You are given an array of unique binary strings, nums, where each string has the same length (say, n). Your task is to return any binary string of length n that is not present in the given array.

Since there are (2^n) possible binary strings of length n and only n strings are present in the input (with (n < 2^n)), at least one binary string is guaranteed not to be in the list.

Examples:

1. Example 1:

   • Input: nums = ["01", "10"]
   • Output: "11"
   • Explanation:
     • The array contains "01" and "10".
     • The string "11" (or "00") does not appear in the array, so "11" is a valid answer.

2. Example 2:

   • Input: nums = ["00", "01"]
   • Output: "10"
   • Explanation:
     • The given binary strings are "00" and "01".
     • The string "10" (or "11") is not in the array, so "10" is a valid answer.

3. Example 3:

   • Input: nums = ["1"]
   • Output: "0"
   • Explanation:
     • The single binary string is "1".
     • The string "0" is not present, making it a valid result.

Constraints:

• The length of the input array is n.
• Each binary string in the array has length n.
• All strings in the array are unique.

Hints Before the Solution

1. Diagonalization Insight:
   Think about how each binary string can be “differentiated” by looking at one character per string. If you look at the i-th character of the i-th string and flip it (change '0' to '1' and vice versa), the resulting string will differ from every string in the list at least at one index.

2. Avoid Brute Force When Possible:
   Although you could generate all possible (2^n) binary strings and check which one is missing, this approach is not efficient. Instead, leverage the guarantee that the array has exactly n strings and use the diagonal method.

Approaches

Approach 1: Diagonalization (Optimal)

Idea:
For each index i (from 0 to n-1), look at the i-th character of the i-th string in the array and flip it. Construct a new binary string from these flipped characters.

Why It Works:

• Assume the resulting string is ans.

• For any string nums[i] in the array, the character at index i in ans is the opposite of the character at index i in nums[i].

• Therefore, ans differs from each nums[i] in at least the i-th position, ensuring it cannot be in the input array.

Time Complexity:

• O(n) iterations with O(1) work per iteration (accessing one character and flipping it), leading to O(n).

• (Note: Since each string is of length n, if you consider reading the entire input, it is O(n²) overall—but the core construction is linear in the number of strings.)

Space Complexity:

• O(n) for constructing the answer string.

Approach 2: Brute Force (Not Recommended)

Idea:
Generate all possible binary strings of length n (there are (2^n) of them) and check each one to see if it is absent from the input array.

Why It's Less Efficient:

• For even moderate values of n, (2^n) grows exponentially.

• Although the input size is small (since n strings of length n implies n is not large), the diagonal method is both elegant and optimal.

Code Implementations

Python Implementation