Problem of The Day: Find Unique Binary String

Problem Statement

Intuition

The problem requires us to find a binary string that is not present in the given list. Since the given list contains unique binary strings of the same length, the idea is to generate possible binary strings recursively and return the first valid one that is not in the list.

Approach

1. Recursive Depth-First Search (DFS):
   • The function dfs generates binary strings by appending ‘0’ or ‘1’ recursively.
   • If the current string reaches the desired length and is not in the input list, we return it as the result.
   • If the string is already in the list, we continue exploring further possibilities.

2. Base Cases:

   • If the current binary string exceeds the required length, return an empty string (invalid case).
   • If a valid string is found that is not in nums, return it immediately.
3. Iteration over “01”:
   • The function iterates over ‘0’ and ‘1’ at each step, ensuring all possible combinations are explored.
   • Once a valid string is found, recursion stops early to improve efficiency.

Complexity

• Time complexity:
  • The worst case scenario explores all possible 2^n binary strings, leading to a time complexity of \(O(2^n)\).
  • However, early stopping optimizes the search significantly.
• Space complexity:
  • The recursion depth is at most n, leading to a space complexity of \(O(n)\) (ignoring the input storage).

Code

from typing import List

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

        def dfs(bin_str, curr):
            if len(curr) > n:
                return ""
            if len(curr) == n and curr not in nums:
                return curr

            res = ""
            for c in bin_str:
                res = dfs(bin_str, curr + c)
                if res != "":
                    return res
            return res

        return dfs("01", "")

Editorial

Approach 1: Recursively Generate All Strings

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        def generate(curr):
            if len(curr) == n:
                if curr not in nums:
                    return curr

                return ""

            add_zero = generate(curr + "0")
            if add_zero:
                return add_zero

            return generate(curr + "1")

        n = len(nums)
        nums = set(nums)
        return generate("")

Approach 2: Iterate Over Integer Equivalents

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        integers = set()
        for num in nums:
            integers.add(int(num, 2))

        n = len(nums)
        for num in range(n + 1):
            if num not in integers:
                ans = bin(num)[2:]
                return "0" * (n - len(ans)) + ans

        return ""