Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Only n of the 2^n binary strings are forbidden. Searching candidate strings in order must therefore find a missing one after at most n + 1 complete candidates. The reference approach uses backtracking rather than diagonal construction.

Approach

Store the input strings in a set. Recursively build a length-n candidate, trying zero before one at each position. At a complete candidate, return it if absent from the set; otherwise signal failure and backtrack. Propagate the first successful string immediately. Increasing prefix length guarantees termination, and the input's size guarantees that some candidate is missing. The generated answer is lexicographically first, although any missing string would be accepted.

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

        def bt(start, curr):
            if start == n:
                if not curr in all:
                    return curr
                return ''

            for num in ('0', '1'):
                next = bt(start + 1, curr + num)
                if next:
                    return next

        return bt(0, '')

Complexity analysis

Let n = nums.length, which is also each string's length. Because only n strings are forbidden, the depth-first lexicographic search reaches at most n + 1 leaves before finding a missing string. Hashing the n input strings and constructing/checking those candidates takes O(n^2) time. Auxiliary space is O(n^2) for simultaneously live immutable recursive prefixes, plus O(n) set entries; the returned string is O(n).