Find Unique Binary String solution and explanation
Google
9 more videos on this problem
Find Unique Binary String - Leetcode Weekly Contest 1980 - PythonNeetCode · 9:02 · 20K views
Find Unique Binary String | Multiple Approaches | Intuition | Leetcode 1980 | codestorywithMIKcodestorywithMIK · 24:44 · 15K views
Find Unique Binary String - Leetcode 1980 - PythonNeetCodeIO · 9:02 · 8K views
Find Unique Binary String | Leetcode 1980Techdose · 9:20 · 2K views
1980. Find Unique Binary String | 3 WaysAryan Mittal · 21:57 · 2K views
1980. Find Unique Binary String (Leetcode Medium)Programming Live with Larry · 5:48 · 656 views
Find Unique Binary String | Leetcode 1980Technosage · 5:37 · 632 views
Daily Leetcode #1325: Nov 16, 2023 - 1980. Find Unique Binary StringProgramming Live with Larry · 15:11 · 390 views
1980. Find Unique Binary String | Leetcode Daily - PythonLeetcode Daily · 6:38 · 357 views
Leetcode | 1980 Find Unique Binary String | Java | BacktrackingCakot Coding · 11:09 · 338 views
The problem
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.length1 <= n <= 16nums[i].length == nnums[i]is either'0'or'1'.- All the strings of
numsare 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.
def find_different_binary_string(nums):
n = len(nums)
return ''.join('1' if nums[i][i] == '0' else '0' for i in range(n))public String findDifferentBinaryString(String[] nums) {
int n = nums.length;
char[] result = new char[n];
for (int i = 0; i < n; i++) {
result[i] = nums[i].charAt(i) == '0' ? '1' : '0';
}
return new String(result);
}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.
Time Complexity: O(n) since we iterate through the array once.
Space Complexity: O(n) for storing the resulting binary string of length n.
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.
function findDifferentBinaryString(nums) {
const set = new Set(nums);
const len = nums.length;
function backtrack(current) {
if (current.length === len) {
if (!set.has(current)) return current;
return null;
}
let res = backtrack(current + '0');
if (res) return res;
return backtrack(current + '1');
}
return backtrack('');
}using System;
using System.Collections.Generic;
public class Solution {
public string FindDifferentBinaryString(string[] nums) {
HashSet<string> set = new HashSet<string>(nums);
string result = string.Empty;
FindBinaryString(set, nums.Length, "", ref result);
return result;
}
private bool FindBinaryString(HashSet<string> set, int len, string current, ref string result) {
if (current.Length == len) {
if (!set.Contains(current)) {
result = current;
return true;
}
return false;
}
if (FindBinaryString(set, len, current + '0', ref result)) return true;
if (FindBinaryString(set, len, current + '1', ref result)) return true;
return false;
}
}The JavaScript solution utilizes recursive backtracking to test each potential binary string until it finds one not included in nums. Each recursive step generates a binary extension by adding a '0' or '1', and depth-first searching ensures uniqueness.
Time Complexity: O(2^n) due to the complete search space of binary strings of length n.
Space Complexity: O(n) from the recursive call stack.
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).
class Solution {
public:
string findDifferentBinaryString(vector<string>& nums) {
int mask = 0;
for (auto& x : nums) {
int cnt = count(x.begin(), x.end(), '1');
mask |= 1 << cnt;
}
for (int i = 0;; ++i) {
if (mask >> i & 1 ^ 1) {
return string(i, '1') + string(nums.size() - i, '0');
}
}
}
};function findDifferentBinaryString(nums: string[]): string {
let mask = 0;
for (let x of nums) {
const cnt = x.split('').filter(c => c === '1').length;
mask |= 1 << cnt;
}
for (let i = 0; ; ++i) {
if (((mask >> i) & 1) === 0) {
return '1'.repeat(i) + '0'.repeat(nums.length - i);
}
}
}func findDifferentBinaryString(nums []string) string {
mask := 0
for _, x := range nums {
mask |= 1 << strings.Count(x, "1")
}
for i := 0; ; i++ {
if mask>>i&1 == 0 {
return strings.Repeat("1", i) + strings.Repeat("0", len(nums)-i)
}
}
}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).
class Solution {
public:
string findDifferentBinaryString(vector<string>& nums) {
int mask = 0;
for (auto& x : nums) {
int cnt = count(x.begin(), x.end(), '1');
mask |= 1 << cnt;
}
for (int i = 0;; ++i) {
if (mask >> i & 1 ^ 1) {
return string(i, '1') + string(nums.size() - i, '0');
}
}
}
};function findDifferentBinaryString(nums: string[]): string {
const n = nums.length;
const ans: string[] = new Array(n);
for (let i = 0; i < n; i++) {
ans[i] = nums[i][i] === '0' ? '1' : '0';
}
return ans.join('');
}func findDifferentBinaryString(nums []string) string {
ans := make([]byte, len(nums))
for i, s := range nums {
if s[i] == '0' {
ans[i] = '1'
} else {
ans[i] = '0'
}
}
return string(ans)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Diagonal Construction Approach | Time Complexity: |
| Backtracking Approach | Time Complexity: |
| Counting + Enumeration | – |
| Construction | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Hash Set | O(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 |
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.