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
- Cantor's diagonal argument: build the answer so that its
i-th bit differs from thei-th bit of thei-th input string. - Then the answer differs from every input string at position
i, so it cannot equal any of them. - This is O(n) and needs no search at all -- a beautiful trick worth remembering.
- A brute-force alternative enumerates all
2^nstrings 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^ncandidates 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 thei-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.