#1980

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find Unique Binary String

Find a binary string of length n not in the input array using array scanning and hash lookup efficiently.

Problem Statement

You are given an array nums of n unique binary strings, each of length n. Return any binary string of length n that does not exist in nums. Multiple valid answers may exist, but only one is required.

For example, if nums = ["01","10"], a valid output is "11" because it is not in nums. Similarly, if nums = ["111","011","001"], an output like "101" would be correct. All input strings consist of only '0' and '1', and n ranges from 1 to 16.

Examples

Example 1

Input: nums = ["01","10"]

Output: "11"

"11" does not appear in nums. "00" would also be correct.

Example 2

Input: nums = ["00","01"]

Output: "11"

"11" does not appear in nums. "10" would also be correct.

Example 3

Input: nums = ["111","011","001"]

Output: "101"

"101" does not appear in nums. "000", "010", "100", and "110" would also be correct.

Constraints

n == nums.length
1 <= n <= 16
nums[i].length == n
nums[i] is either '0' or '1'.
All the strings of nums are unique.

Solution Approach

Convert Strings to Integers

Map each binary string to its integer representation to allow O(1) hash lookups. Scan from 0 to 2^n - 1 and return the first integer not present in the set converted back to a binary string of length n.

Backtracking Generation

Use backtracking to generate all possible binary strings of length n. At each step, check the current string against the hash set of nums and return once a missing string is found. This ensures no duplicates and respects input constraints.

Diagonal Method Shortcut

Construct a binary string by flipping the i-th bit of the i-th string in nums. This guarantees a unique string different from all nums entries at least in one position, providing a quick O(n) solution without full scanning.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because each string check or construction involves iterating through n strings of length n. Space complexity is O(1) if using in-place construction or minimal auxiliary storage for hash sets.

What Interviewers Usually Probe

Will you convert strings to integers for faster lookup?
Can you explain how backtracking can generate a valid missing string?
Is there a direct O(n) way without checking all 2^n candidates?

Common Pitfalls or Variants

Common pitfalls

Assuming only one correct output exists instead of recognizing multiple valid strings.
Failing to maintain fixed string length when converting integers back to binary.
Attempting naive iteration over all 2^n strings, which can exceed time limits for n=16.

Follow-up variants

Return all missing binary strings instead of any single one.
Find a unique binary string with additional constraints on number of 1s.
Handle larger n efficiently by using bit manipulation tricks.

FAQ

What is the simplest approach to find a unique binary string in this problem?

Use a hash set to store all input strings, then generate candidates by integer conversion or backtracking until a missing string is found.

Can multiple correct outputs exist for Find Unique Binary String?

Yes, any binary string of length n not in nums is valid, so multiple answers are acceptable.

How does the diagonal method guarantee a unique string?

By flipping the i-th bit of the i-th string, the resulting string differs from each input string in at least one position.

Is converting binary strings to integers necessary?

Not strictly, but it allows O(1) lookup in a hash set and simplifies candidate generation for larger n.

What is the time complexity pattern for this problem?

The array scanning plus hash lookup pattern ensures O(n) time, avoiding full enumeration of all 2^n strings.

terminal

Solution

Solution 1: Counting + Enumeration

Since the number of `'1'`s in a binary string of length $n$ can be $0, 1, 2, \cdots, n$ (a total of $n + 1$ possibilities), we can always find a new binary string whose count of `'1'`s differs from every string in $\textit{nums}$.

1

2

3

4

5

6

7

8

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        mask = 0
        for x in nums:
            mask |= 1 << x.count("1")
        for i in count(0):
            if mask >> i & 1 ^ 1:
                return "1" * i + "0" * (len(nums) - i)

Solution 2: Construction

We can construct a binary string $\textit{ans}$ of length $n$, where the $i$-th bit of $\textit{ans}$ differs from the $i$-th bit of $\textit{nums}[i]$. Since all strings in $\textit{nums}$ are distinct, $\textit{ans}$ will not appear in $\textit{nums}$.

1

2

3

4

5

6

7

8

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        mask = 0
        for x in nums:
            mask |= 1 << x.count("1")
        for i in count(0):
            if mask >> i & 1 ^ 1:
                return "1" * i + "0" * (len(nums) - i)

Continue Practicing

#1948 delete duplicate folders in system #2023 number of pairs of strings with concatenation equal to target #2053 kth distinct string in an array