Find Unique Binary String
MedPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves generating all possible binary strings of length n one by one and checking if they exist in the input array nums. To make the checking process efficient, we first convert the input array nums into a HashSet. The first generated string that is not found in the HashSet is our answer.
Algorithm
- Create a
HashSet<String>and add all elements from the input arraynumsto it. This allows for efficient O(1) average time lookups. - Iterate with an integer counter, let's say
i, starting from 0 up to2^n - 1. - In each iteration, convert the integer
ito its binary string representation. - Pad the generated binary string with leading zeros to ensure its length is
n. - Check if this newly formed
n-bit binary string is present in theHashSet. - If the string is not in the set, it means we have found a unique binary string. Return this string.
- Since there are
nstrings innumsout of2^ntotal possibilities, a unique string is guaranteed to be found.
Walkthrough
The total number of distinct binary strings of length n is 2^n. We can represent each of these strings by an integer from 0 to 2^n - 1. The algorithm proceeds as follows:
First, we insert all strings from nums into a HashSet. This data structure provides average O(1) time complexity for checking the existence of an element. Building this set takes O(n^2) time as we have n strings of length n.
Next, we iterate from i = 0 upwards. In each step, we convert the integer i into its n-bit binary string representation. For instance, if n=4 and i=5, the binary is 101, which we pad to 0101. We then check if this generated string is present in our HashSet.
If the string is not in the set, we have found a unique string and can return it immediately. The problem guarantees that nums contains n unique strings, and since 2^n > n for n >= 1, there's always at least one missing string. We are sure to find an answer, at worst, after checking n+1 possibilities.
import java.util.HashSet;import java.util.Set; class Solution { public String findDifferentBinaryString(String[] nums) { Set<String> numSet = new HashSet<>(); for (String s : nums) { numSet.add(s); } int n = nums.length; for (int i = 0; i < (1 << n); i++) { String binary = Integer.toBinaryString(i); // Format to n-bit string with leading zeros String formattedBinary = String.format("%" + n + "s", binary).replace(' ', '0'); if (!numSet.contains(formattedBinary)) { return formattedBinary; } } return ""; // Should not be reached given the problem constraints }}Complexity
Time
O(n^2). Creating the `HashSet` takes `O(n * n)` time. The subsequent loop runs at most `n+1` times, and inside the loop, string generation and hash set lookup each take `O(n)` time. Thus, the total time complexity is dominated by `O(n^2)`.
Space
O(n^2). The `HashSet` stores `n` strings, each of length `n`, leading to a space requirement proportional to the total number of characters.
Trade-offs
Pros
Straightforward and easy to understand.
It is guaranteed to find a solution.
Cons
Inefficient in terms of both time and space compared to the optimal solution.
Requires significant extra space to store the HashSet, which can be large for greater values of
n.
This approach builds a candidate binary string character by character using recursion. It explores the search space of all possible binary strings by appending '0' and '1' at each step. The search is pruned as soon as a valid unique string is found, avoiding unnecessary exploration.
Algorithm
- First, add all strings from
numsinto aHashSetfor quick lookups. - Define a recursive function, for example
generate(currentBuilder), that attempts to build a unique binary string. - Base Case: If the length of
currentBuilderequalsn, check if the resulting string is in theHashSet. If it's not, return the string. Otherwise, return a signal (e.g.,null) indicating this path failed. - Recursive Step:
- Append '0' to
currentBuilderand make a recursive call. If the call returns a valid string, propagate it up and return. - If not, backtrack by removing the '0'.
- Append '1' to
currentBuilderand make another recursive call. If this call finds a string, return it. - If not, backtrack again.
- If both branches fail, return
null.
- Append '0' to
- Initiate the process by calling the recursive function with an empty
StringBuilder.
Walkthrough
Instead of generating numbers and converting them to strings, we can build the string directly using recursion. We start with an empty string and at each step, we have two choices: append a '0' or a '1'. This process forms a binary tree of possibilities.
To begin, we store all strings from nums in a HashSet for efficient O(1) lookups. We then define a recursive function that takes the currently built string (e.g., in a StringBuilder) as an argument.
The recursion's base case is when the string's length reaches n. At this point, we check if the constructed string exists in our HashSet. If it doesn't, we've found our answer and return it. If it does, we return a special value like null to signify that this path did not yield a solution.
In the recursive step, we first try appending '0' and making a recursive call. If that call returns a valid string, we immediately pass it up the call stack. If not, we backtrack (remove the '0') and try appending '1', making another recursive call. If either path is successful, the search terminates early.
import java.util.HashSet;import java.util.Set; class Solution { private Set<String> numSet; private int n; public String findDifferentBinaryString(String[] nums) { this.numSet = new HashSet<>(); for (String s : nums) { numSet.add(s); } this.n = nums.length; return backtrack(new StringBuilder()); } private String backtrack(StringBuilder current) { if (current.length() == n) { String result = current.toString(); if (!numSet.contains(result)) { return result; } return null; } // Try appending '0' current.append('0'); String found = backtrack(current); if (found != null) { return found; } current.deleteCharAt(current.length() - 1); // Backtrack // Try appending '1' current.append('1'); found = backtrack(current); if (found != null) { return found; } current.deleteCharAt(current.length() - 1); // Backtrack return null; }}Complexity
Time
O(n^2). Building the set takes `O(n^2)`. The backtracking function will explore paths until a solution is found. Since a solution is guaranteed to be found after checking at most `n+1` leaf nodes, the complexity of the search is proportional to `n` (depth) * `n` (leaf check), resulting in `O(n^2)` overall.
Space
O(n^2). The `HashSet` requires `O(n^2)` space. The recursion depth adds `O(n)` to the call stack, which is subdominant.
Trade-offs
Pros
Provides a systematic way to explore the search space.
It is a general-purpose technique (backtracking) applicable to many problems.
Finds a solution without generating all
2^npossibilities.
Cons
More complex to implement compared to an iterative brute-force approach.
Has the same asymptotic time and space complexity as the simpler brute-force method.
For very large
n(not an issue here asn <= 16), recursion could lead to stack overflow errors.
This is a highly efficient and elegant approach that leverages a concept from set theory known as Cantor's diagonalization argument. We can construct a new binary string that is guaranteed to be different from every string in the input array by ensuring it differs from the i-th string at the i-th position.
Algorithm
- Initialize an empty
StringBuilderto construct the result string. - Iterate with an index
ifrom0ton-1, wherenis the number of strings. - In each iteration, look at the
i-th character of thei-th string (nums[i].charAt(i)). - Append the opposite character to the
StringBuilder. Ifnums[i].charAt(i)is '0', append '1'; if it's '1', append '0'. - After the loop finishes, convert the
StringBuilderto a string and return it.
Walkthrough
The key insight is that we don't need to know all the missing strings; we just need to find one. We can construct such a string directly. Let the result string be res.
We can make res different from nums[0] by ensuring res.charAt(0) is different from nums[0].charAt(0). We can make res different from nums[1] by ensuring res.charAt(1) is different from nums[1].charAt(1). We can generalize this for all i from 0 to n-1.
The algorithm is as follows: we build our result string character by character. For the i-th character of our result, we look at the i-th character of the i-th input string, nums[i]. We then choose the flipped bit for our result. That is, if nums[i].charAt(i) is '0', the i-th character of our result will be '1', and vice versa.
After iterating from i=0 to n-1, we will have a new string of length n. This string is guaranteed to be unique because, by construction, it differs from every nums[i] in at least one position (the i-th position). This method avoids any need for extra data structures like sets and is extremely fast.
class Solution { public String findDifferentBinaryString(String[] nums) { StringBuilder ans = new StringBuilder(); for (int i = 0; i < nums.length; i++) { // Get the character from the diagonal (i-th char of i-th string) char ch = nums[i].charAt(i); // Append the opposite character to the result ans.append(ch == '0' ? '1' : '0'); } return ans.toString(); }}Complexity
Time
O(n). We perform a single pass through the input array. In each of the `n` iterations, we do a constant number of operations (character access and append).
Space
O(n) to store the `StringBuilder` for the result. If the space for the output is not counted, the complexity is O(1).
Trade-offs
Pros
Extremely efficient with linear time complexity.
Minimal space complexity, as it doesn't require any auxiliary data structures like a HashSet.
The implementation is very simple and concise.
Cons
The underlying concept (diagonalization) might be less immediately obvious than a brute-force search.
Solutions
Solution
public class Solution { public string FindDifferentBinaryString(string[] nums) { int mask = 0; foreach(var x in nums) { int cnt = x.Count(c => c == '1'); mask |= 1 << cnt; } int i = 0; while ((mask >> i & 1) == 1) { i++; } return string.Format("{0}{1}", new string('1', i), new string('0', nums.Length - i)); }}class Solution {public String findDifferentBinaryString(String[] nums) { int mask = 0; for (var x : nums) { int cnt = 0; for (int i = 0; i < x.length(); ++i) { if (x.charAt(i) == '1') { ++cnt; } } mask |= 1 << cnt; } for (int i = 0;; ++i) { if ((mask >> i & 1) == 0) { return "1".repeat(i) + "0".repeat(nums.length - i); } } }}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'); } } }};class Solution: def findDifferentBinaryString(self, nums: List[str]) -> str: mask = 0 for x in nums: mask |= 1 << x . count("1") n = len(nums) for i in range(n + 1): if mask >> i & 1 ^ 1: return "1" * i + "0" * (n - i)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.