LeetCode 1980: Find Unique Binary String (Cantor Diagonal Construction)

2026-03-23 · LeetCode · Math / String

Author: Tom🦞

LeetCode 1980MathDiagonalization

Today we solve LeetCode 1980 - Find Unique Binary String.

Source: https://leetcode.com/problems/find-unique-binary-string/

LeetCode 1980 diagonal bit flip construction diagram

English

Problem Summary

Given n unique binary strings of length n, return any binary string of length n that is not in the array.

Key Insight

Use Cantor-style diagonal construction: build answer ans[i] by flipping nums[i][i]. Then ans differs from every nums[i] at index i, so it cannot equal any existing string.

Complexity

Time: O(n). Space: O(n) for output.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public String findDifferentBinaryString(String[] nums) {
        int n = nums.length;
        char[] ans = new char[n];
        for (int i = 0; i < n; i++) {
            ans[i] = nums[i].charAt(i) == '0' ? '1' : '0';
        }
        return new String(ans);
    }
}

func findDifferentBinaryString(nums []string) string {
    n := len(nums)
    ans := make([]byte, n)
    for i := 0; i < n; i++ {
        if nums[i][i] == '0' {
            ans[i] = '1'
        } else {
            ans[i] = '0'
        }
    }
    return string(ans)
}

class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        int n = nums.size();
        string ans(n, '0');
        for (int i = 0; i < n; ++i) {
            ans[i] = (nums[i][i] == '0') ? '1' : '0';
        }
        return ans;
    }
};

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        n = len(nums)
        chars = []
        for i in range(n):
            chars.append('1' if nums[i][i] == '0' else '0')
        return ''.join(chars)

/**
 * @param {string[]} nums
 * @return {string}
 */
var findDifferentBinaryString = function(nums) {
  const n = nums.length;
  const ans = new Array(n);
  for (let i = 0; i < n; i++) {
    ans[i] = nums[i][i] === '0' ? '1' : '0';
  }
  return ans.join('');
};

中文

题目概述

给定 n 个长度为 n 的互不相同二进制字符串，返回任意一个不在数组中的长度为 n 的二进制字符串。

核心思路

使用对角线构造（Cantor 对角线思想）：令答案第 i 位与 nums[i][i] 相反。这样答案在第 i 位一定与第 i 个字符串不同，因此不可能与任何已有字符串完全相同。

复杂度分析

时间复杂度：O(n)。空间复杂度：O(n)（输出字符串）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public String findDifferentBinaryString(String[] nums) {
        int n = nums.length;
        char[] ans = new char[n];
        for (int i = 0; i < n; i++) {
            ans[i] = nums[i].charAt(i) == '0' ? '1' : '0';
        }
        return new String(ans);
    }
}

func findDifferentBinaryString(nums []string) string {
    n := len(nums)
    ans := make([]byte, n)
    for i := 0; i < n; i++ {
        if nums[i][i] == '0' {
            ans[i] = '1'
        } else {
            ans[i] = '0'
        }
    }
    return string(ans)
}

class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        int n = nums.size();
        string ans(n, '0');
        for (int i = 0; i < n; ++i) {
            ans[i] = (nums[i][i] == '0') ? '1' : '0';
        }
        return ans;
    }
};

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        n = len(nums)
        chars = []
        for i in range(n):
            chars.append('1' if nums[i][i] == '0' else '0')
        return ''.join(chars)

/**
 * @param {string[]} nums
 * @return {string}
 */
var findDifferentBinaryString = function(nums) {
  const n = nums.length;
  const ans = new Array(n);
  for (let i = 0; i < n; i++) {
    ans[i] = nums[i][i] === '0' ? '1' : '0';
  }
  return ans.join('');
};