# Find Unique Binary String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-unique-binary-string)
Canonical: https://scaleengineer.com/dsa/problems/find-unique-binary-string
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** Array, Hash Table, String
---
## Problem
Given an array of strings `nums` containing `n` **unique** binary strings each of length `n`, return _a binary string of length_ `n` _that **does not appear** in_ `nums`_. If there are multiple answers, you may return **any** of them_.

**Example 1:**

**Input:** nums = ["01","10"]
**Output:** "11"
**Explanation:** "11" does not appear in nums. "00" would also be correct.

**Example 2:**

**Input:** nums = ["00","01"]
**Output:** "11"
**Explanation:** "11" does not appear in nums. "10" would also be correct.

**Example 3:**

**Input:** nums = ["111","011","001"]
**Output:** "101"
**Explanation:** "101" does not appear in nums. "000", "010", "100", and "110" would also be correct.

**Constraints:**

* `n == nums.length`
* `1 <= n <= 16`
* `nums[i].length == n`
* `nums[i] `is either `'0'` or `'1'`.
* All the strings of `nums` are **unique**.

# Approaches
## Brute Force by Generating and Checking
This approach involves generating all possible binary strings of length `n` one by one and checking if they exist in the input array `nums`. To make the checking process efficient, we first convert the input array `nums` into a `HashSet`. The first generated string that is not found in the `HashSet` is our answer.
**Time:** O(n^2). Creating the `HashSet` takes `O(n * n)` time. The subsequent loop runs at most `n+1` times, and inside the loop, string generation and hash set lookup each take `O(n)` time. Thus, the total time complexity is dominated by `O(n^2)`. · **Space:** O(n^2). The `HashSet` stores `n` strings, each of length `n`, leading to a space requirement proportional to the total number of characters.
**Pros:** Straightforward and easy to understand.; It is guaranteed to find a solution.
**Cons:** Inefficient in terms of both time and space compared to the optimal solution.; Requires significant extra space to store the HashSet, which can be large for greater values of `n`.
### Explanation
The total number of distinct binary strings of length `n` is `2^n`. We can represent each of these strings by an integer from `0` to `2^n - 1`. The algorithm proceeds as follows:

First, we insert all strings from `nums` into a `HashSet`. This data structure provides average O(1) time complexity for checking the existence of an element. Building this set takes O(n^2) time as we have `n` strings of length `n`.

Next, we iterate from `i = 0` upwards. In each step, we convert the integer `i` into its `n`-bit binary string representation. For instance, if `n=4` and `i=5`, the binary is `101`, which we pad to `0101`. We then check if this generated string is present in our `HashSet`.

If the string is not in the set, we have found a unique string and can return it immediately. The problem guarantees that `nums` contains `n` unique strings, and since `2^n > n` for `n >= 1`, there's always at least one missing string. We are sure to find an answer, at worst, after checking `n+1` possibilities.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public String findDifferentBinaryString(String[] nums) {
        Set<String> numSet = new HashSet<>();
        for (String s : nums) {
            numSet.add(s);
        }
        
        int n = nums.length;
        for (int i = 0; i < (1 << n); i++) {
            String binary = Integer.toBinaryString(i);
            // Format to n-bit string with leading zeros
            String formattedBinary = String.format("%" + n + "s", binary).replace(' ', '0');
            
            if (!numSet.contains(formattedBinary)) {
                return formattedBinary;
            }
        }
        
        return ""; // Should not be reached given the problem constraints
    }
}
```
### Algorithm
- Create a `HashSet<String>` and add all elements from the input array `nums` to it. This allows for efficient O(1) average time lookups.
- Iterate with an integer counter, let's say `i`, starting from 0 up to `2^n - 1`.
- In each iteration, convert the integer `i` to its binary string representation.
- Pad the generated binary string with leading zeros to ensure its length is `n`.
- Check if this newly formed `n`-bit binary string is present in the `HashSet`.
- If the string is not in the set, it means we have found a unique binary string. Return this string.
- Since there are `n` strings in `nums` out of `2^n` total possibilities, a unique string is guaranteed to be found.

## Recursive Backtracking
This approach builds a candidate binary string character by character using recursion. It explores the search space of all possible binary strings by appending '0' and '1' at each step. The search is pruned as soon as a valid unique string is found, avoiding unnecessary exploration.
**Time:** O(n^2). Building the set takes `O(n^2)`. The backtracking function will explore paths until a solution is found. Since a solution is guaranteed to be found after checking at most `n+1` leaf nodes, the complexity of the search is proportional to `n` (depth) * `n` (leaf check), resulting in `O(n^2)` overall. · **Space:** O(n^2). The `HashSet` requires `O(n^2)` space. The recursion depth adds `O(n)` to the call stack, which is subdominant.
**Pros:** Provides a systematic way to explore the search space.; It is a general-purpose technique (backtracking) applicable to many problems.; Finds a solution without generating all `2^n` possibilities.
**Cons:** More complex to implement compared to an iterative brute-force approach.; Has the same asymptotic time and space complexity as the simpler brute-force method.; For very large `n` (not an issue here as `n <= 16`), recursion could lead to stack overflow errors.
### Explanation
Instead of generating numbers and converting them to strings, we can build the string directly using recursion. We start with an empty string and at each step, we have two choices: append a '0' or a '1'. This process forms a binary tree of possibilities.

To begin, we store all strings from `nums` in a `HashSet` for efficient O(1) lookups. We then define a recursive function that takes the currently built string (e.g., in a `StringBuilder`) as an argument.

The recursion's base case is when the string's length reaches `n`. At this point, we check if the constructed string exists in our `HashSet`. If it doesn't, we've found our answer and return it. If it does, we return a special value like `null` to signify that this path did not yield a solution.

In the recursive step, we first try appending '0' and making a recursive call. If that call returns a valid string, we immediately pass it up the call stack. If not, we backtrack (remove the '0') and try appending '1', making another recursive call. If either path is successful, the search terminates early.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    private Set<String> numSet;
    private int n;

    public String findDifferentBinaryString(String[] nums) {
        this.numSet = new HashSet<>();
        for (String s : nums) {
            numSet.add(s);
        }
        this.n = nums.length;
        return backtrack(new StringBuilder());
    }

    private String backtrack(StringBuilder current) {
        if (current.length() == n) {
            String result = current.toString();
            if (!numSet.contains(result)) {
                return result;
            }
            return null;
        }

        // Try appending '0'
        current.append('0');
        String found = backtrack(current);
        if (found != null) {
            return found;
        }
        current.deleteCharAt(current.length() - 1); // Backtrack

        // Try appending '1'
        current.append('1');
        found = backtrack(current);
        if (found != null) {
            return found;
        }
        current.deleteCharAt(current.length() - 1); // Backtrack

        return null;
    }
}
```
### Algorithm
- First, add all strings from `nums` into a `HashSet` for quick lookups.
- Define a recursive function, for example `generate(currentBuilder)`, that attempts to build a unique binary string.
- **Base Case:** If the length of `currentBuilder` equals `n`, check if the resulting string is in the `HashSet`. If it's not, return the string. Otherwise, return a signal (e.g., `null`) indicating this path failed.
- **Recursive Step:**
  - Append '0' to `currentBuilder` and make a recursive call. If the call returns a valid string, propagate it up and return.
  - If not, backtrack by removing the '0'.
  - Append '1' to `currentBuilder` and make another recursive call. If this call finds a string, return it.
  - If not, backtrack again.
  - If both branches fail, return `null`.
- Initiate the process by calling the recursive function with an empty `StringBuilder`.

## Diagonalization Method (Cantor's Argument)
This is a highly efficient and elegant approach that leverages a concept from set theory known as Cantor's diagonalization argument. We can construct a new binary string that is guaranteed to be different from every string in the input array by ensuring it differs from the `i`-th string at the `i`-th position.
**Time:** O(n). We perform a single pass through the input array. In each of the `n` iterations, we do a constant number of operations (character access and append). · **Space:** O(n) to store the `StringBuilder` for the result. If the space for the output is not counted, the complexity is O(1).
**Pros:** Extremely efficient with linear time complexity.; Minimal space complexity, as it doesn't require any auxiliary data structures like a HashSet.; The implementation is very simple and concise.
**Cons:** The underlying concept (diagonalization) might be less immediately obvious than a brute-force search.
### Explanation
The key insight is that we don't need to know all the missing strings; we just need to find one. We can construct such a string directly. Let the result string be `res`.

We can make `res` different from `nums[0]` by ensuring `res.charAt(0)` is different from `nums[0].charAt(0)`. We can make `res` different from `nums[1]` by ensuring `res.charAt(1)` is different from `nums[1].charAt(1)`. We can generalize this for all `i` from `0` to `n-1`.

The algorithm is as follows: we build our result string character by character. For the `i`-th character of our result, we look at the `i`-th character of the `i`-th input string, `nums[i]`. We then choose the flipped bit for our result. That is, if `nums[i].charAt(i)` is '0', the `i`-th character of our result will be '1', and vice versa.

After iterating from `i=0` to `n-1`, we will have a new string of length `n`. This string is guaranteed to be unique because, by construction, it differs from every `nums[i]` in at least one position (the `i`-th position). This method avoids any need for extra data structures like sets and is extremely fast.

```java
class Solution {
    public String findDifferentBinaryString(String[] nums) {
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < nums.length; i++) {
            // Get the character from the diagonal (i-th char of i-th string)
            char ch = nums[i].charAt(i);
            // Append the opposite character to the result
            ans.append(ch == '0' ? '1' : '0');
        }
        return ans.toString();
    }
}
```
### Algorithm
- Initialize an empty `StringBuilder` to construct the result string.
- Iterate with an index `i` from `0` to `n-1`, where `n` is the number of strings.
- In each iteration, look at the `i`-th character of the `i`-th string (`nums[i].charAt(i)`).
- Append the opposite character to the `StringBuilder`. If `nums[i].charAt(i)` is '0', append '1'; if it's '1', append '0'.
- After the loop finishes, convert the `StringBuilder` to a string and return it.

# Solutions
### CSharp

```csharp
public class Solution {
    public string FindDifferentBinaryString(string[] nums) {
        int mask = 0;
        foreach(var x in nums) {
            int cnt = x.Count(c => c == '1');
            mask |= 1 << cnt;
        }
        int i = 0;
        while ((mask >> i & 1) == 1) {
            i++;
        }
        return string.Format("{0}{1}", new string('1', i), new string('0', nums.Length - i));
    }
}
```

### Java

```java
class Solution {
public
  String findDifferentBinaryString(String[] nums) {
    int mask = 0;
    for (var x : nums) {
      int cnt = 0;
      for (int i = 0; i < x.length(); ++i) {
        if (x.charAt(i) == '1') {
          ++cnt;
        }
      }
      mask |= 1 << cnt;
    }
    for (int i = 0;; ++i) {
      if ((mask >> i & 1) == 0) {
        return "1".repeat(i) + "0".repeat(nums.length - i);
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  string findDifferentBinaryString(vector<string> &nums) {
    int mask = 0;
    for (auto &x : nums) {
      int cnt = count(x.begin(), x.end(), '1');
      mask |= 1 << cnt;
    }
    for (int i = 0;; ++i) {
      if (mask >> i & 1 ^ 1) {
        return string(i, '1') + string(nums.size() - i, '0');
      }
    }
  }
};

```

### Python

```python
class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str: mask = 0 for x in nums: mask |= 1 << x . count("1") n = len(nums) for i in range(n + 1): if mask >> i & 1 ^ 1: return "1" * i + "0" * (n - i)

```