Skip to main content
Talentd

Find Unique Binary String - Solution & Explanation

MediumArrayHash TableStringBacktracking16 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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.

 

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. "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.

Approach Overview

Problem Overview: You receive n unique binary strings, each of length n. The goal is to construct another binary string of length n that does not appear in the list. Since there are 2^n possible binary strings but only n are provided, at least one valid answer must exist.

Approach 1: Backtracking with Hash Set (O(2^n * n) time, O(n) space)

Store all given strings in a hash set for constant‑time lookup. Then use backtracking to generate every possible binary string of length n. At each recursion step, append either '0' or '1' and continue until the string length reaches n. Once a candidate is built, check if it exists in the set. If it does not, return it immediately. The generation process explores up to 2^n possibilities and each membership check costs O(n) for string comparison, leading to O(2^n * n) time complexity. This method clearly demonstrates the search space and is easy to reason about, but it becomes inefficient for larger n.

Approach 2: Diagonal Construction (Cantor's Argument) (O(n) time, O(n) space)

The optimal approach uses a clever observation inspired by Cantor’s diagonalization. Look at the i-th string and flip its i-th bit: if it is '0', use '1'; otherwise use '0'. Append this flipped bit to your result string. After processing all n positions, the constructed string differs from the i-th input string at position i. That guarantees the result cannot match any string in the list. The algorithm only iterates once through the input array (array) and performs constant work per index, giving O(n) time and O(n) space for the output string. The approach relies purely on string manipulation and does not require extra data structures.

Recommended for interviews: Interviewers expect the diagonal construction solution. It shows you recognize the constraint that each string differs at a specific index, which eliminates the need to search the full space. Starting with the backtracking idea demonstrates understanding of the problem space, but moving to the O(n) diagonal solution shows strong algorithmic insight and familiarity with constructive proofs used in algorithm design.

Approach 1: Diagonal Construction Approach

This approach builds a unique binary string by considering each string's diagonal to ensure uniqueness. Specifically, we take advantage of the fact that flipping a bit diagonally guarantees that it differs from the original set of strings across at least one position. For each string at index i, we flip the character at the same index i, ensuring that the constructed string cannot match any existing strings due to its diagonal differentiation.

The Python solution generates a binary string by iterating over each index i of the strings in nums. At each index, it checks the diagonal bit nums[i][i] and inverts it. This results in a binary string that is guaranteed to be different from any given string in nums due to the difference along the diagonal.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n) since we iterate through the array once.
Space Complexity: O(n) for storing the resulting binary string of length n.

Try this approach in the editor →

Approach 2: Backtracking Approach

This approach uses backtracking to generate all possible binary strings of length n and checks for the first one not present in nums. While not as efficient as diagonal construction, this method demonstrates a different strategy to ensure a solution's validity by exhaustive search.

The C# solution employs a backtracking method to explore every binary string possibility. If a binary string of the required length isn't in nums, it is identified as the result. The use of a recursive helper function facilitates generating possible candidates one bit at a time.

Code

C#JavaScript

C#

JavaScript

Complexity

Time Complexity: O(2^n) due to generating every binary string of length n.
Space Complexity: O(n) for the call stack during recursion.

Try this approach in the editor →

Approach 3: 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 nums.

We use an integer mask to record the counts of '1's across all strings, where the i-th bit of mask being 1 indicates that a binary string of length n with exactly i occurrences of '1' exists in nums, and 0 otherwise.

We then enumerate i starting from 0, representing the count of '1's in a binary string of length n. If the i-th bit of mask is 0, it means no binary string of length n with exactly i occurrences of '1' exists, and we can return that string as the answer.

The time complexity is O(L), where L is the total length of all strings in nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptJavaScriptC#

Python

Java

C++

Go

TypeScript

JavaScript

C#

Try this approach in the editor →

Approach 4: Construction

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

The time complexity is O(n), where n is the length of the strings in nums. Ignoring the space used by the answer string, the space complexity is O(1).

Code

JavaC#C++JavaScriptGoPythonTypeScript

Java

C#

C++

JavaScript

Go

Python

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Diagonal Construction Approach

Time Complexity: O(n) since we iterate through the array once.
Space Complexity: O(n) for storing the resulting binary string of length n.

Backtracking Approach

Time Complexity: O(2^n) due to generating every binary string of length n.
Space Complexity: O(n) for the call stack during recursion.

Counting + Enumeration—
Construction—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking with Hash SetO(2^n * n)O(n)Useful for understanding the full search space or when demonstrating recursive generation of binary strings
Diagonal Construction (Cantor's Argument)O(n)O(n)Best approach for interviews and production; guarantees a unique string in linear time

Video Solution

Find Unique Binary String - Leetcode Weekly Contest 1980 - Python • NeetCode • 20,345 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Unique Binary String easy or hard?
The problem is rated Medium because the brute-force idea is straightforward but inefficient. Recognizing the diagonal construction trick requires a deeper insight into how to guarantee a different string without checking all possibilities.
Find Unique Binary String Python/Java solution
In Python or Java, implement the diagonal idea by iterating from 0 to n-1 and appending the opposite bit of nums[i][i] to a result builder. Python typically uses a list or string join, while Java uses a StringBuilder. Both implementations run in O(n) time.
How to solve Find Unique Binary String in O(n)?
Use diagonal construction. For each index i from 0 to n-1, check the i-th string’s i-th character and flip it (0 → 1, 1 → 0). Append the flipped bit to the result. The resulting string differs from every given string at position i, guaranteeing it is unique.
What is the best approach for Find Unique Binary String?
The best approach is diagonal construction based on Cantor’s diagonal argument. Flip the i-th bit of the i-th string and append it to the result. The constructed string differs from every input string at least at one index, guaranteeing uniqueness. This runs in O(n) time and O(n) space.
Is Find Unique Binary String asked at Google/Amazon/Meta?
This type of constructive string problem appears in interviews at companies like Google, Amazon, and Meta because it tests logical reasoning rather than brute force. Interviewers expect recognition of the diagonal argument or another linear-time construction.
What data structure is used in Find Unique Binary String?
The optimal solution mainly uses string construction and simple array indexing. The alternative backtracking approach uses a hash set to store existing strings and perform O(1) membership checks while generating candidates.
What is the time complexity of Find Unique Binary String?
The optimal diagonal construction solution runs in O(n) time because it iterates once through the n input strings and flips a single bit from each. Space complexity is O(n) for building the result string. A brute-force backtracking approach takes O(2^n * n) time.

Ready to solve this problem?

Practice Find Unique Binary String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find All Numbers Disappeared in an Array

Next

Missing Number