1980. Find Unique Binary String - Explanation

1. Backtracking (Recursion)

Intuition

We need to find any binary string of length n that is not in the given array. Since there are 2^n possible strings but only n strings in the input, at least one must be missing. We can systematically try building strings character by character, checking at each complete string whether it exists in the set.

Algorithm

Store all input strings in a hash set for O(1) lookup.
Use backtracking starting with a string of all zeros.
At position i:
- If i == n, check if the current string is in the set. If not, return it.
- Try keeping position i as '0' and recurse.
- If that fails, change position i to '1' and recurse.
Return the first string not found in the set.

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        strSet = {s for s in nums}

        def backtrack(i, cur):
            if i == len(nums):
                res = "".join(cur)
                return None if res in strSet else res

            res = backtrack(i + 1, cur)
            if res: return res

            cur[i] = "1"
            return backtrack(i + 1, cur)

        return backtrack(0, ["0" for _ in nums])

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Backtracking (Iteration)

Intuition

Instead of recursive backtracking, we can iterate through all possible binary strings from 0 to n (we only need n+1 candidates since there are n input strings). Convert each number to its binary representation, pad it to length n, and check if it exists in the set.

Algorithm

Store all input strings in a hash set.
Iterate num from 0 to n:
- Convert num to a binary string and pad with leading zeros to length n.
- If this string is not in the set, return it.
Return empty string (though we are guaranteed to find one within n+1 attempts).

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        strSet = set(nums)
        n = len(nums)

        for num in range(1 << n):
            res = bin(num)[2:].zfill(n)
            if res not in strSet:
                return res

        return ""

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

3. Cantor's Diagonal Argument

Intuition

Cantor's diagonal argument provides an elegant O(n) solution. For each string nums[i], we look at its i-th character and flip it. The resulting string differs from nums[0] at position 0, from nums[1] at position 1, and so on. This guarantees the constructed string differs from every input string at at least one position.

Algorithm

Create an empty result string.
For each index i from 0 to n-1:
- Look at character nums[i][i] (the diagonal).
- Append the opposite character: if it is '0', append '1'; if '1', append '0'.
Return the result string.

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        res = []
        for i in range(len(nums)):
            if nums[i][i] == '0':
                res.append('1')
            else:
                res.append('0')
        return "".join(res)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(1)$ extra space.
- $O(n)$ space for the output string.

4. Randomization

Intuition

Since there are 2^n possible strings but only n are in the input, randomly generating a string has a high probability of being unique. For small n, this probability is at least (2^n - n) / 2^n, which approaches 1 quickly. We keep generating random strings until we find one not in the set.

Algorithm

Store all input strings in a hash set.
Loop indefinitely:
- Generate a random binary string of length n by randomly choosing '0' or '1' for each position.
- If the string is not in the set, return it.
The expected number of attempts is very small due to the sparsity of input strings.

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        strSet = set(nums)
        n = len(nums)

        while True:
            res = "".join(random.choice("01") for _ in range(n))
            if res not in strSet:
                return res

Time & Space Complexity

Time complexity: $O(∞)$ in worst case.
Space complexity: $O(n)$

5. Trie

Intuition

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.

Algorithm

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.
Pad the result with '1's to reach length n if needed.
Return the constructed string.

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)

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

Common Pitfalls

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.