We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Unique Binary String

Number: 2107

Difficulty: Medium

Paid? No

Companies: Google, Meta, Microsoft, Bloomberg

Problem Description

Given an array of unique binary strings where the number of strings is equal to the length of each string, return a new binary string of the same length that does not occur in the array. If there are multiple possible answers, you may return any one of them.

Key Insights

  • Use a diagonalization strategy to guarantee the new string is different from each input string.
  • For each index i, flip the i-th bit of the i-th string:
    • If the bit is '0', change it to '1'; if it is '1', change it to '0'.
  • This guarantees that the resulting string differs from the i-th input string at least at the i-th position.
  • The approach avoids generating and checking all possible strings.

Space and Time Complexity

Time Complexity: O(n), where n is the number of strings (each string length is n, but we only access one bit per string).
Space Complexity: O(n) for storing the resulting string.

Solution

The solution uses a simple diagonalization technique. By iterating through the list of strings and flipping the bit at the position corresponding to the string’s index, we ensure that the newly constructed string has a different bit in the diagonal positions compared to each of the original strings. This difference in at least one position for every string prevents the result from matching any of the input strings.

Code Solutions

# Function to find a unique binary string not present in the input array.
def findUniqueBinaryString(nums):
    # Initialize a list to store the characters of the resulting string.
    result = []
    # Iterate over the array with index.
    for i, num in enumerate(nums):
        # Flip the bit at the i-th position.
        if num[i] == '0':
            result.append('1')
        else:
            result.append('0')
    # Join the list into a final string and return it.
    return "".join(result)

# Example usage:
nums = ["01", "10"]
print(findUniqueBinaryString(nums))  # Possible output: "11" or another valid string.
← Back to All Questions