Find Unique Binary String

Problem Description

Given an array of strings nums containing n unique binary strings each of length n, return a binary string of length n that does not appear in nums. If there are multiple answers, you may return any of them.

Key Insights

• The binary strings are of fixed length n and are unique within the given array.
• The possible binary strings of length n are 2^n, but only n of them are provided in the array.
• One effective way to find a unique binary string is to utilize the concept of a diagonal approach, where we can construct a new binary string based on the input strings.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can construct a new binary string by iterating through the input strings and choosing the opposite bit from the diagonal. This ensures that the new string is different from each string in the input array. This approach guarantees that the generated string is unique and adheres to the required length.

1. Initialize an empty string for the result.
2. For each index i from 0 to n-1, append the opposite bit of the i-th string's i-th character to the result. This means if the character is '0', append '1', and if it's '1', append '0'.
3. Return the constructed string.

Code Solutions