Logo

Kode$word

LeetCode 1980: Find Unique Binary String – Multiple Ways to Generate a Missing Binary Combination
LeetCode 1980: Find Unique Binary String – Multiple Ways to Generate a Missing Binary Combination

LeetCode 1980: Find Unique Binary String – Multiple Ways to Generate a Missing Binary Combination

A Complete Guide to Solving “Find Unique Binary String” Using Hashing, Brute Force Thinking, and Cantor’s Diagonalization

13 views
0
0
Binary StringsHashingCantor DiagonalizationLeetCodeMedium
Github icon

Try the Problem

You can solve the problem here:

https://leetcode.com/problems/find-unique-binary-string/


Problem Description

You are given an array nums containing n unique binary strings, where each string has length n.

Your task is to return any binary string of length n that does not appear in the array.

Important Conditions

  1. Each string consists only of '0' and '1'.
  2. Every string in the array is unique.
  3. The output must be a binary string of length n.
  4. If multiple valid answers exist, any one of them is acceptable.


Examples

Example 1

Input

nums = ["01","10"]

Output

"11"

Explanation

Possible binary strings of length 2:

00
01
10
11

Since "01" and "10" are already present, valid answers could be:

00 or 11

Example 2

Input

nums = ["00","01"]

Output

"11"

Another valid output could be:

10

Example 3

Input

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

Output

101

Other valid answers include:

000
010
100
110

Constraints

n == nums.length
1 <= n <= 16
nums[i].length == n
nums[i] consists only of '0' and '1'
All strings in nums are unique

Important Observation

The total number of binary strings of length n is:

2^n

But the array contains only:

n strings

Since 2^n grows very quickly and n ≤ 16, there are many possible binary strings missing from the array. Our goal is simply to construct one of those missing strings.


Thinking About the Problem

Before jumping into coding, it's useful to think about different strategies that could help us generate a binary string that does not appear in the array.

Possible Ways to Think About the Problem

When approaching this problem, several ideas may come to mind:

  1. Generate all possible binary strings of length n and check which one is missing.
  2. Store all strings in a HashSet or HashMap and construct a candidate string to verify whether it exists.
  3. Manipulate existing strings by flipping bits to create new combinations.
  4. Use a mathematical trick that guarantees the new string is different from every string in the list.

Each of these approaches leads to a different solution strategy.

In this article, we will walk through these approaches and understand how they work.


Approach 1: Brute Force – Generate All Binary Strings

Idea

The simplest idea is to generate every possible binary string of length n and check whether it exists in the given array.

Since there are:

2^n possible binary strings

We can generate them one by one and return the first string that does not appear in nums.

Steps

  1. Convert numbers from 0 to (2^n - 1) into binary strings.
  2. Pad the binary string with leading zeros so its length becomes n.
  3. Check if that string exists in the array.
  4. If not, return it.

Time Complexity

O(2^n * n)

This works because n is at most 16, but it is still not the most elegant approach.


Approach 2: HashMap + Bit Flipping (My Approach)

Idea

While solving this problem, another idea is to store all given binary strings inside a HashMap for quick lookup.

Then we can try to construct a new binary string by flipping bits from the existing strings.

The intuition is simple:

  1. If the current character is '0', change it to '1'.
  2. If the current character is '1', change it to '0'.

By flipping bits at different positions, we attempt to build a new binary combination.

Once the string is constructed, we check whether it already exists in the map.

If the generated string does not exist, we return it as our answer.


Java Implementation (My Solution)

class Solution {

public String findDifferentBinaryString(String[] nums) {

int len = nums[0].length();

// HashMap to store all given binary strings
HashMap<String, Integer> mp = new HashMap<>();

for(int i = 0; i < nums.length; i++){
mp.put(nums[i], i);
}

int cou = 0;
String ans = "";

for(int i = 0; i < nums.length; i++){

if(cou < len){

// Flip the current bit
if(nums[i].charAt(cou) == '0'){
ans += '1';
cou++;
}
else{
ans += '0';
cou++;
}

}else{

// If generated string does not exist in map
if(!mp.containsKey(ans)){
return ans;
}

// Reset and try building again
ans = "";
cou = 0;
}
}

return ans;
}
}

Time Complexity

O(n²)

Because we iterate through the array and perform string operations.

Space Complexity

O(n)

For storing the strings in the HashMap.


Approach 3: Cantor’s Diagonalization (Optimal Solution)

Idea

A clever mathematical observation allows us to construct a string that must differ from every string in the array.

We build a new string such that:

  1. The first character differs from the first string.
  2. The second character differs from the second string.
  3. The third character differs from the third string.

And so on.

By ensuring that the generated string differs from each string at least at one position, it is guaranteed not to exist in the array.

This technique is known as Cantor’s Diagonalization.


Java Implementation

class Solution {

public String findDifferentBinaryString(String[] nums) {

int n = nums.length;

StringBuilder result = new StringBuilder();

for(int i = 0; i < n; i++){

// Flip the diagonal bit
if(nums[i].charAt(i) == '0'){
result.append('1');
}
else{
result.append('0');
}
}

return result.toString();
}
}

Time Complexity

O(n)

We only traverse the array once.

Space Complexity

O(n)

For storing the resulting string.


Comparison of Approaches

ApproachTime ComplexitySpace ComplexityNotes
Brute ForceO(2^n * n)O(n)Simple but inefficient
HashMap + Bit FlippingO(n²)O(n)Constructive approach
Cantor DiagonalizationO(n)O(n)Optimal and elegant


Key Takeaways

This problem highlights an interesting concept in algorithm design:

Sometimes the best solution is not searching for the answer but constructing one directly.

By understanding the structure of the input, we can generate a result that is guaranteed to be unique.


Conclusion

The Find Unique Binary String problem can be solved using multiple strategies, ranging from brute force enumeration to clever mathematical construction.

While brute force works due to the small constraint (n ≤ 16), more elegant solutions exist. Using hashing or constructive approaches improves efficiency and demonstrates deeper algorithmic thinking.

Among all approaches, the Cantor Diagonalization technique provides the most efficient and mathematically guaranteed solution.

Understanding problems like this helps strengthen skills in string manipulation, hashing, and constructive algorithms, which are commonly tested in coding interviews.

Related Articles

Find Minimum in Rotated Sorted Array – Binary Search Explained | LeetCode Medium 153

Find Minimum in Rotated Sorted Array – Binary Search Explained | LeetCode Medium 153

LeetCode 153 – Find the minimum element in a rotated sorted array in O(log n) time.

Read Article
Minimum Changes to Make Alternating Binary String – LeetCode 1758 Explained

Minimum Changes to Make Alternating Binary String – LeetCode 1758 Explained

Understand how to convert a binary string into an alternating pattern with the minimum number of flips using a simple greedy approach.

Read Article
Check if Binary String Has at Most One Segment of Ones – Java Solution (LeetCode 1784)

Check if Binary String Has at Most One Segment of Ones – Java Solution (LeetCode 1784)

Learn how to determine whether a binary string contains only one continuous group of 1s. This article explains the problem clearly, builds the intuition step-by-step, and walks through a clean Java solution with time complexity analysis.

Read Article
Find All Duplicates in an Array

Find All Duplicates in an Array

LeetCode Question 442

Read Article

Ai Assistant Kas