Leetcode Sunday #5

LeetCode 1980: Find Unique Binary String

Difficulty: Medium

Despite this problem being labelled as a Medium problem, I found this challenge more approachable than expected once I understood the key idea.

The Problem

We are given an array nums containing unique binary strings, all of the same length n. The goal is to return any binary string of length n that does not exist in the array.

At first glance, the problem seems to require generating and checking many possible binary strings until we find one that isn’t in the list.

My First Thought

Since the problem explicitly says the binary strings are unique, my first instinct was to use a map:

• The key would be the binary string.
• The value would be a boolean (true).

This way, I could quickly check whether a generated string already existed in the array.

check := make(map[string]bool)
for _, s := range nums {
    check[s] = true
}

The idea of this structure was to help prevent returning a string that already appears in nums.

The Hard Part: Generating a Unique Binary String

The bigger challenge was now how to construct a binary string that is guaranteed not to exist in the input.

Since binary strings only contain two digits: 0 and 1's, one idea was to flip bits:

0 → 1

1 → 0

then would flip the bits recursively until I get the unique binary string, but somewhere along the lines, I realised that this was not the way to go since I was not getting to what I wanted to achieve. This led me to try a different approach.

A Better Insight

The breakthrough came when I started comparing characters across different strings.

Consider this example:

1010
1111
0101
0000

Initially, I would compare the values of all four binary strings at a given index to come up with the final flipped binary. Instead of that, I was now flipping the combinations diagonally to come up with the final binary.

• Look at the index-th string
• Flip the index-th bit

example:

Index	Original Bit	Flipped Bit
nums[0][0]	1	0
nums[1][1]	1	0
nums[2][2]	0	1
nums[3][3]	0	1

This approach gave me mostly all the time a unique value.

My Implementation

Here is the Go implementation I wrote:

func findDifferentBinaryString(nums []string) string {
    ret := []rune{}
    check := make(map[string]bool)

    for i, s := range nums {
        check[s] = true

        if s[i] == '0' {
            ret = append(ret, '1')
        } else {
            ret = append(ret, '0')
        }
    }

    if !check[string(ret)] {
        return string(ret)
    }

    return ""
}

Possible Optimisation

Since by diagonally flipping the values, the generated string is guaranteed to be unique, I could have simplified the code as:

func findDifferentBinaryString(nums []string) string {
    ret := make([]rune, 0, len(nums))

    for i, s := range nums {
        if s[i] == '0' {
            ret = append(ret, '1')
        } else {
            ret = append(ret, '0')
        }
    }

    return string(ret)
}

I decided to move forward with the first aproach so if at all I come up with a duplicate binary string, only an empty string would be returned, signifying that there was an error in binary generation.

Lastly

Sometimes the best solution isn't usually about generating more possibilities, but about constructing the right one directly.