Reading Section: 1980. Find Unique Binary String

Problem Statement:
You are given an array of n unique binary strings, each of length n.
You need to return a binary string of length n that does not appear in the array.
If there are multiple possible answers, return any of them.

Example 1

Input:
nums = ["01", "10"]
Output:
"11"
Explanation:
"11" does not appear in nums. "00" would also be correct.

Example 2

Input:
nums = ["00", "01"]
Output:
"11"
Explanation:
"11" does not appear in nums. "10" would also be correct.

Example 3

Input:
nums = ["111", "011", "001"]
Output:
"101"
Explanation:
"101" does not appear in nums.
Other possible correct answers: "000", "010", "100", "110".

Constraints

• n == nums.length

• 1 <= n <= 16

• nums[i].length == n

• Each nums[i] is made of '0' or '1'

• All strings in nums are unique

Approach 1: Brute Force using Set (O(2ⁿ × n) Time, O(2ⁿ × n) Space)

Idea:
There are 2ⁿ possible binary strings of length n.
We can generate all of them, then check which one does not exist in nums.

Steps:

1. Insert all strings from nums into a hash set for quick lookup.

2. For each integer i from 0 to 2ⁿ - 1:

   • Convert i into a binary string of length n.

   • If this string is not found in the set, return it.

3. This guarantees finding one missing string.

Complexity:

• Time: O(2ⁿ × n) because we generate and check every binary string.

• Space: O(2ⁿ × n) due to storing all strings in a set.

This approach is simple but not efficient for large n.

Approach 2: Diagonal Approach (O(n) Time, O(n) Space)

Idea:
This method uses the diagonalization concept.
For each string nums[i], look at the character at index i and flip it.
This ensures the final string is different from every nums[i] at least in one position.

Steps:

1. Let n = nums.size().

2. Create an empty string result.

3. For each i in range 0 to n-1:

   • If nums[i][i] == '0', append '1'.

   • Otherwise, append '0'.

4. Return result.

Complexity:

• Time: O(n)

• Space: O(n)

This is the optimal and elegant solution.

C++ Code

class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        int n = nums.size();
        string result = "";
        for (int i = 0; i < n; i++) {
            if (nums[i][i] == '0') {
                result += '1';
            } else {
                result += '0';
            }
        }
        return result;   
    }
};