Show problems as
Classic problem #1980MediumArrayHash TableStringBacktracking

Find Unique Binary String

Real-world version: An Unissued Badge Code
Tracked in this browser only
Read Find Unique Binary String on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A depot stamps access badges with fixed-width codes. A code of width n is a row of n characters where each character is either 0 or 1.

You are handed nums, the list of codes already stamped. It holds exactly n codes, every one of them of width n, and no two of them are the same.

Return a code of width n, again built only from the characters 0 and 1, that does not appear in nums. Usually more than one code qualifies. When that happens, return the qualifying code that comes earliest in dictionary order.

There are 2^n codes of width n and nums lists only n of them, so a qualifying code always exists.

Examples

Example 1

Input
nums = ["000", "001", "010"]
Output
"011"

`011` has width three, uses only `0` and `1`, and is not one of the three stamped codes. Every width-three code ahead of it in dictionary order, namely `000`, `001` and `010`, is stamped.

Example 2

Input
nums = ["1101", "0000", "1000", "0111"]
Output
"0001"

`0001` is unstamped, while `0000` is stamped, so nothing earlier in dictionary order qualifies.

Example 3

Input
nums = ["11010", "01001", "10111", "00011", "11100"]
Output
"00000"

None of the five stamped codes is `00000`, and no width-five code precedes it in dictionary order.

Constraints

  • n == nums.length
  • 1 <= n <= 16
  • nums[i].length == n
  • Every character of nums[i] is either '0' or '1'.
  • No code appears twice in nums.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def find_different_binary_string(nums: list[str]) -> str:
Java
public String findDifferentBinaryString(String[] nums)

More on the same topics