Find Unique Binary String
Medium · Backtracking · Array · Hash Table · String · Backtracking
Problem
You are given an array nums of n distinct binary strings, each of length n. Return a binary string of length n that does not appear in nums.
If several strings are missing, return any one of them: every correct answer is accepted.
Examples
Input: nums = ["00","01"] Output: "10"
"10" is not in the list; "11" would also be accepted.
Input: nums = ["111","011","001"] Output: "000"
"000" is not in the list, and several other answers are equally valid.
Input: nums = ["0"] Output: "1"
With length 1, the only other string is "1".
Constraints
- n == len(nums)
- 1 <= n <= 16
- len(nums[i]) == n
- nums[i] consists only of '0' and '1'
- All strings in nums are distinct
Approaches
- Baseline: try the numbers 0, 1, 2, … in order — time O(n²), space O(n²)
Follow-up
The diagonal trick is Cantor's argument: it builds a string unlike every string in a list, however the list is chosen. If instead the answer must be a specific missing string, such as the smallest one, you need to search (the first use case). Asking whether every string of length k appears, inside one long string, turns the question around (the second).
Related problems
Start free on Cariara · Coding problems · System design studio
