Find Unique Binary 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.

Examples

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.

Solution

We are tasked with generating a binary string of length n that does not exist in the input array nums.

Video explanation

Here is the video explaining below methods in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/Q1nLccIrljM" frameborder="0" allowfullscreen></iframe></div>

Method 1 - Convert to number and find first not in set

By converting binary strings to integers, we can work with numbers and significantly simplify operations like determining what's missing. Let's break this approach step by step:

Here is the approach:

1. Convert Binary Strings to Integer Values:
   • Each binary string in nums is converted to an integer using the binary-to-decimal conversion.
   • For example, the binary string "001" becomes the integer 1 (in base 10).
2. Store Integer Values in a HashSet:
   • Add all integer representations of the binary strings to a HashSet for quick lookups.
3. Find the First Missing Integer:
   • Since the total number of binary strings of length n is 2^n, iterate from 0 to 2^n - 1. The first number not found in the HashSet is the desired result.
4. Convert the Missing Number Back to a Binary String:
   • Convert the integer back to a binary string of length n using built-in libraries, ensuring leading zeroes are preserved.

Code

Java

class Solution {
    public String findDifferentBinaryString(String[] nums) {
        int n = nums.length;
        Set<Integer> numSet = new HashSet<>();
        
        // Convert binary strings to integers and add to HashSet
        for (String num : nums) {
            numSet.add(Integer.parseInt(num, 2));  // Convert binary to integer
        }
        
        // Iterate from 0 to 2^n - 1 and find the first missing number
        for (int i = 0; i < (1 << n); i++) {  // Iterate up to 2^n
            if (!numSet.contains(i)) {
                // Convert the missing number back to a binary string with leading zeroes
                return String.format("%" + n + "s", Integer.toBinaryString(i)).replace(' ', '0');
            }
        }
        
        return "";  // Shouldn't reach here as there's always a missing binary string
    }
}

Python

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        n = len(nums)
        
        # Convert binary strings to their integer values
        num_set = set(int(num, 2) for num in nums)
        
        # Iterate from 0 to 2^n - 1 and find the first missing number
        for num in range(2**n):
            if num not in num_set:
                # Convert the missing number back to a binary string
                return format(num, f'0{n}b')  # `f'0{n}b'` ensures the result has leading zeroes

Complexity

• ⏰ Time complexity: O(n^2)
  • Converting each binary string in nums to its integer representation (O(n) per string for parsing, assuming nums[i] is of length n) and adding it to the HashSet occurs for n strings. Total cost: O(n²) (O(n) parsing cost × n strings).
  • The missing number is found by iterating over integers from 0 to 2^n - 1, performing an O(1) membership lookup in the HashSet.
    • However, due to the optimization, we exit the loop as soon as we find the first missing number:
    • At worst, we perform n iterations in practice because there is always at least one missing binary string when nums is of size n.
    • Membership checks in a HashSet run in O(1).
  • Converting the missing number (an integer) back to a binary string of length n uses O(n) logic.
• 🧺 Space complexity: O(n^2). - Contains up to n integers (integer representations of input binary strings), which is O(n) in space.

Method 2 - Recursion and Backtracking

Here is the approach:

1. Convert the array nums into a HashSet:
   • HashSet makes it efficient (O(1) lookup time) to check if a particular binary string exists in nums.
2. Use Backtracking to Generate Binary Strings:
   • Start from an empty string and iteratively try to build every possible binary string of length n using "0" and "1".
   • As soon as a binary string is generated that doesn't exist in the HashSet, return it immediately.
3. This approach systematically generates binary strings and leverages the HashSet to ensure we don’t return a string that's already in nums.

Code

Java

class Solution {
    public String findDifferentBinaryString(String[] nums) {
        int n = nums.length;
        Set<String> numSet = new HashSet<>();
        for (String s : nums) {
            numSet.add(s);  // Add all strings to a HashSet for quick lookup
        }

        // Start the backtracking process from an empty string
        return backtrack("", n, numSet);
    }

    // Helper function to perform backtracking
    private String backtrack(String curr, int n, Set<String> numSet) {
        if (curr.length() == n) {  // If the string is of length `n`
            return numSet.contains(curr) ? "" : curr;  // Return if it doesn't exist
        }

        // Try appending "0" and "1"
        String res = backtrack(curr + "0", n, numSet);  // Try with "0"
        if (!res.isEmpty()) {
            return res;  // If a valid result is found, stop further recursion
        }
        return backtrack(curr + "1", n, numSet);  // Otherwise, try "1"
    }
}

Python

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        n: int = len(nums)
        num_set: Set[str] = set(nums)  # Store all strings in a hash set for fast lookup

        # Backtracking function to generate strings
        def backtrack(curr: str) -> str:
            if len(curr) == n:  # If the string is of length `n`
                return curr if curr not in num_set else ""  # Return if it doesn't exist
            
            # Try appending "0" and "1"
            res = backtrack(curr + "0")  # Try with "0"
            if res:  # If a valid result is found, stop further recursion
                return res
            return backtrack(curr + "1")  # Otherwise, try "1"
        
        # Start the backtracking with an empty string
        return backtrack("")

Complexity

• ⏰ Time complexity: O(n^2)
  • We need to convert nums, a list of n binary strings each of length n, into a HashSet to enable O(1) lookups.
    • The cost of adding a single string of length n to a HashSet is O(n).
    • For n strings, the total cost is O(n * n), i.e., O(n²).
  • We have n binary strings in nums, and since we search only for missing strings, at most we perform up to O(n) iterations (as there is one missing binary string).
  • At each recursive call:
    • A string concatenation operation (curr + "0" or curr + "1") occurs. This operation requires creating a new string of size up to n in Java, which costs O(n).
  • Given that string concatenations occur for each recursive call, the overall cost of the backtracking process is bounded by O(n * n), since we generate up to O(n) binary strings during the recursion, and each operation costs O(n).
• 🧺 Space complexity: O(n^2)
  • The dominating costs are the O(n²) for HashSet construction and O(n²) for backtracking.

Method 3 - Genius Solution using Cantor's Diagonal Argument

Since all strings are unique so we just need to check ith bit of ith string and put its opposite in our answer

One of the clean and effective strategies to ensure uniquely generating such a binary string is leveraging the diagonal approach (related to the Cantor Diagonalisation argument). Here's the reasoning for the approach:

1. Constructing the Diagonal String:
   • For every index i (0-indexed), take the complement (flip) of the binary value ('0' -> '1' and '1' -> '0') from the string located at index i and position i in the array nums.
2. The constructed string is guaranteed not to exist in nums because it differs from the string at index i specifically in the i-th position.
3. Return this constructed (complemented diagonal) string.

Here is how the dry run will work:

Code

Java

class Solution {
    public String findDifferentBinaryString(String[] nums) {
        int n = nums.length;
        char[] ans = new char[n];
        
        // Build the diagonal string by flipping characters
        for (int i = 0; i < n; i++) {
            // Flip the character at index (i, i)
            char flipped = nums[i].charAt(i) == '0' ? '1' : '0';
            ans[i] = flipped;
        }
        
        return new String(ans);
    }
}

Python

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        n: int = len(nums)
        ans: str = ""

        # Build the diagonal string by flipping characters
        for i in range(n):
            flipped: str = '1' if nums[i][i] == '0' else '0'
            ans += flipped
        
        return ans

Complexity

• ⏰ Time complexity: O(n) as we iterate over nums exactly once, extracting and flipping the diagonal elements to construct the new binary string.
• 🧺 Space complexity: O(n), as the space is used to store the result string ans of length n.