Find Unique Binary String
Medium · Backtracking · Explanation and code example
Trie
How it works
A Trie (prefix tree) stores all input strings and allows us to find a missing string by traversing the tree. At each node, if one of the two children (0 or 1) is missing, we can take that path and fill the rest arbitrarily. This finds a missing string in O(n) time after O(n^2) preprocessing.
Steps
- Build a Trie by inserting all input strings.
- Traverse the Trie from the root:
- At each node, check if the
'0'or'1'child is missing. - If
'0'is missing, append'0'and return (fill remaining with any character). - If
'1'is missing, append'1'and return. - If both exist, prefer
'1'and continue deeper.
- At each node, check if the
- Pad the result with
'1's to reach lengthnif needed. - Return the constructed string.
Complexity
- Time complexity:
O(n ^ 2) - Space complexity:
O(n ^ 2)
Things to watch for
Iterating Through All 2^n Possibilities
Since there are only n input strings but 2^n possible strings of length n, a missing string is guaranteed to exist. However, iterating through all 2^n possibilities is exponential and will time out for larger n. The optimal approach only needs to check n+1 candidates or use Cantor's diagonal argument.
Forgetting to Pad Binary Strings with Leading Zeros
When converting integers to binary strings, the result may be shorter than n characters. Forgetting to pad with leading zeros (e.g., "1" instead of "001" for n=3) will cause the generated string to have incorrect length and fail comparison with input strings.
Misunderstanding Cantor's Diagonal Argument
The diagonal approach flips the i-th character of the i-th string to guarantee the result differs from every input. A common mistake is flipping at fixed positions (like always the first character) or not understanding why the diagonal specifically ensures uniqueness.
Python code example
from typing import List
class Node:
def __init__(self):
self.children = [None, None]
def contains_bit(self, bit: int) -> bool:
return self.children[bit] is not None
def put(self, bit: int):
self.children[bit] = Node()
def get(self, bit: int):
return self.children[bit]
class Trie:
def __init__(self):
self.root = Node()
def insert(self, s: str):
curr = self.root
for c in s:
bit = int(c)
if not curr.contains_bit(bit):
curr.put(bit)
curr = curr.get(bit)
def search(self, res: str, curr) -> bool:
while curr.contains_bit(0) or curr.contains_bit(1):
if not curr.contains_bit(0):
res.append('0')
return True
if not curr.contains_bit(1):
res.append('1')
return True
res.append('1')
curr = curr.get(1)
return False
class Solution:
def findDifferentBinaryString(self, nums: List[str]) -> str:
trie = Trie()
for s in nums:
trie.insert(s)
res = []
trie.search(res, trie.root)
while len(res) < len(nums):
res.append('1')
return ''.join(res)
C++ code example
class Node {
public:
Node *children[2];
Node() {
this->children[0] = nullptr;
this->children[1] = nullptr;
}
bool containsBit(int bit) {
return this->children[bit] != nullptr;
}
void put(int bit) {
this->children[bit] = new Node();
}
Node* get(int bit) {
return this->children[bit];
}
};
class Trie {
public:
Node* root;
Trie() {
this->root = new Node();
}
void insert(const string& s) {
Node* curr = root;
for (char c : s) {
int bit = c - '0';
if (!curr->containsBit(bit)) {
curr->put(bit);
}
curr = curr->get(bit);
}
}
bool search(string& res, Node* curr) {
while (curr->containsBit(0) || curr->containsBit(1)) {
if (!curr->containsBit(0)) {
res += '0';
return true;
}
if (!curr->containsBit(1)) {
res += '1';
return true;
}
res += '1';
curr = curr->get(1);
}
return false;
}
};
class Solution {
public:
string findDifferentBinaryString(vector<string>& nums) {
Trie trie;
for (const string& s : nums) {
trie.insert(s);
}
string res;
trie.search(res, trie.root);
while (res.length() < nums.size()) {
res += '1';
}
return res;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.