⚡Flashcard Drill➔
NeetCode #505LC-1980MediumBacktracking
← Back to All Problems

#505 · #1980 · Find Unique Binary String(找到不同的二进制字符串)

📌 Problem Statement & Constraints

Given an array of n unique binary strings each of length n, return a binary string of length n that does not appear in the array. Constraints: 1 <= n <= 16, all strings have length n and are unique.

💡 Core Algorithmic Approaches

  1. Cantor's diagonal argument: build the answer so that its i-th bit differs from the i-th bit of the i-th input string.
  2. Then the answer differs from every input string at position i, so it cannot equal any of them.
  3. This is O(n) and needs no search at all -- a beautiful trick worth remembering.
  4. A brute-force alternative enumerates all 2^n strings and checks membership, which is O(n * 2^n).

💻 Benchmark Python3 Implementation

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        # diagonalisation: flip the i-th bit of the i-th string
        return "".join("1" if nums[i][i] == "0" else "0" for i in range(len(nums)))

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass over the strings.
💾 Space Complexity
O(n) for the result.

⚠️ Interview Pitfalls & Follow-ups

  • Enumerating all 2^n candidates and testing membership: correct but far slower than the diagonal argument.
  • Flipping a fixed position instead of the diagonal: the result might coincide with an input string.
  • Assuming the answer must be a permutation of some input: it need not be.
  • Off-by-one on the diagonal: the i-th bit of the i-th string, both 0-indexed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems