Beat 100% of solutions from Leet code problem 1980: 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.
https://leetcode.com/problems/find-unique-binary-string/

Intuition

his method generates binary strings by flipping individual bits and checks if each generated string is in the input list nums. It returns the first binary string found that is not in the list.

Approach

The solution systematically generates binary strings by flipping individual bits and checks whether each generated string is in the input list nums. If a binary string is found in the list, it continues the process by flipping the next bit. The loop continues until it finds a binary string that is not present in the list nums or until the position exceeds the length of the binary string.

The solution leverages the fact that the binary string can be represented as a list of characters, allowing for easy manipulation of individual bits. The algorithm efficiently explores possible binary strings until it finds one that satisfies the given conditions.

Initialize a binary string (result) with all zeros, represented by a list of characters (chars) containing '0' repeated as many times as there are elements in the input list nums.

Use a while loop to iterate until a binary string is found that is not present in the input list nums or until the position (k) exceeds the length of the binary string.

Inside the loop:

Convert the current binary string (result) into a list of characters (chars).
Flip the bit at the current position (k) in the binary string.
Update the binary string (result) with the modified list of characters.
Increment the position (k) to move to the next bit.
Return the binary string that is not present in the input list nums.

Complexity

• Time complexity: O(n * m):

  The while loop runs until a binary string is found that is not in the list nums or until the position k exceeds the length of the binary string. In the worst case, this loop iterates through all possible binary strings of length m.

  Within the loop, operations such as converting the binary string to a list of characters, flipping a bit, and joining the characters back into a string all take O(m) time.

• Space complexity: O(m)

chars: A list of characters representing the current binary string. The length of this list is equal to the length of each binary string in nums (m). Therefore, the space complexity for chars is O(m).

result: The binary string constructed from the chars list. The space complexity for result is also O(m).

k: An integer variable used to keep track of the position in the binary string. This variable requires constant space, O(1).

The input list nums and the class itself do not contribute to the space complexity as they are not dependent on the size of the input.

Code Python

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        chars = ['0'] * len(nums)
        result = ''.join(chars)
        k = 0
        while(result in nums and k < len(result)):
            chars = list(result)
            chars[k] = '1' if chars[k] == '0' else '0'
            result = ''.join(chars)
            k += 1
        return result   

Code JS

function findDifferentBinaryString(nums: string[]): string {
    let result = '0'.repeat(nums.length);
    let k = 0;

    while (nums.includes(result) && k < result.length) {
        result = result.slice(0, k) + (result[k] === '0' ? '1' : '0') + result.slice(k + 1);
        k += 1;
    }

    return result;  
}

Code in Ruby

def find_different_binary_string(nums)
    chars = ['0'] * nums.length
    result = chars.join('')
    k = 0

    while nums.include?(result) && k < result.length
      chars = result.chars
      chars[k] = (chars[k] == '0' ? '1' : '0')
      result = chars.join('')
      k += 1
    end

    result
end