1980-find Unique String (Day-08)

Interview Trick: Find a Binary String Not Present in the Array

One interesting interview problem asks:

Problem

You are given n unique binary strings of length n.
Return any binary string of length n that does not appear in the array.

Example:

Input:
nums = ["01","10"]

Output:
"11"   // or "00"

---

Brute Force Idea

Since each string has length n, there are:

2^n

possible binary strings.

If we generate all 2^n strings and check which one is missing from the array, we can solve the problem.

However, this approach is inefficient.

Time Complexity

O(2^n * n)

---

Optimal Interview Trick (Diagonal Method)

A much smarter approach uses a concept similar to Cantor’s Diagonalization.

Idea:

Construct a new string by flipping the diagonal bit of each string.

ans[i] = flip(nums[i][i])

Where:

0 → 1
1 → 0

---

Why This Works

For every index i:

ans[i] ≠ nums[i][i]

That means the constructed string differs from the i-th string at position i.

Therefore:

• ans ≠ nums[0]
• ans ≠ nums[1]
• ...
• ans ≠ nums[n-1]

So the new string cannot exist in the array.

---

Example

nums = ["010",
        "111",
        "000"]

Diagonal bits:

0 1 0

Flip them:

1 0 1

Result:

"101"

This string differs from every string in nums.

---

C++ Implementation

class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        int n = nums.size();
        string ans = "";

        for(int i = 0; i < n; i++) {
            if(nums[i][i] == '0')
                ans += '1';
            else
                ans += '0';
        }

        return ans;
    }
};

---

Complexity

Time Complexity

O(n)

Space Complexity

O(n)

---

Key Interview Insight

Whenever you see:

• n binary strings
• each of length n
• need a missing string

Think:

Flip the diagonal bits.

This guarantees a string different from every given string.