Find Unique Binary String - Video Solutions

Problem Overview: You receive n unique binary strings, each of length n. The goal is to construct another binary string of length n that does not appear in the list. Since there are 2^n possible binary strings but only n are provided, at least one valid answer must exist.

Approach 1: Backtracking with Hash Set (O(2^n * n) time, O(n) space)

Store all given strings in a hash set for constant‑time lookup. Then use backtracking to generate every possible binary string of length n. At each recursion step, append either '0' or '1' and continue until the string length reaches n. Once a candidate is built, check if it exists in the set. If it does not, return it immediately. The generation process explores up to 2^n possibilities and each membership check costs O(n) for string comparison, leading to O(2^n * n) time complexity. This method clearly demonstrates the search space and is easy to reason about, but it becomes inefficient for larger n.

Approach 2: Diagonal Construction (Cantor's Argument) (O(n) time, O(n) space)

The optimal approach uses a clever observation inspired by Cantor’s diagonalization. Look at the i-th string and flip its i-th bit: if it is '0', use '1'; otherwise use '0'. Append this flipped bit to your result string. After processing all n positions, the constructed string differs from the i-th input string at position i. That guarantees the result cannot match any string in the list. The algorithm only iterates once through the input array (array) and performs constant work per index, giving O(n) time and O(n) space for the output string. The approach relies purely on string manipulation and does not require extra data structures.

Recommended for interviews: Interviewers expect the diagonal construction solution. It shows you recognize the constraint that each string differs at a specific index, which eliminates the need to search the full space. Starting with the backtracking idea demonstrates understanding of the problem space, but moving to the O(n) diagonal solution shows strong algorithmic insight and familiarity with constructive proofs used in algorithm design.