> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/weekly-contest/1980.-find-unique-binary-string-cantors-diagonalization.md).

# 1980. Find Unique Binary String - Cantor's Diagonalization

```
T: O(n)
S: O(n)
```

````java
```java
class Solution {
    public String findDifferentBinaryString(String[] nums) {
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i].charAt(i) == '0') {
                result.append('1');
            } else {
                result.append('0');
            }        
        }
        return result.toString();
    }
}

/**
T: O(n)
S: O(n)
  01. 10
  /.    \
  1      1. -> ans!!!


  ["111","011","001"]
    /      |       \
    0      0        0 -> ans!!!!

 */
```
````

## Backtracking

* **Time Complexity: O(2^n)**.
* **Space Complexity: O(n^2)**.

```java
class Solution {
    public String findDifferentBinaryString(String[] nums) {
        int n = nums.length;
        char[] arr = new char[]{'0', '1'};
        String[] result = new String[1];
        Set<String> set = new HashSet<>();
        for (String num : nums) {
            set.add(num);
        }
        dfs(n, set, result, new StringBuilder(), arr);

        return result[0];
    }
    private void dfs(int n, Set<String> nums, String[] result, StringBuilder cur, char[] arr) {
        if (result[0] != null) {
            return;
        }
        if (cur.length() == n) {
            if (!nums.contains(cur.toString()) && result[0] == null) {
                result[0] = cur.toString();
            }
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            cur.append(arr[i]);
            dfs(n, nums, result, cur, arr);
            cur.deleteCharAt(cur.length()-1);
        }
    }
}
```