# LeetCode 1980. Find Unique Binary String

# Approach 1: Recursive

## Intuition

- Since the maximum possible length of
`nums`

is $2^{16} = 65536$, which is not so big. As a consequence, it’s possible to solve this problem recursively. - During the recursion, we can either choose from adding a zero
`"0"`

or adding a one`"1"`

to the string. - Try generating a unique string of length

## Approach

- Convert
`nums`

to a set`unique`

. - Try generating a string from an empty string
`s`

:- Try adding a zero (
`"0"`

) to the end of`s`

. - If adding a zero is not possible (i.e., the string after adding a zero is a member of
`unique`

), try adding a one (`"1"`

). - If the length of
`s`

euqals to`nums.size()`

and`s`

is not a member of`unique`

, then return`s`

. - Otherwise, return an empty string.

- Try adding a zero (

Pseudocode of this approach:

1 | generate(s, maxLen, unique): |

## Complexity

Time complexity:

- $n$ calls to generate a unique string of length $n$.
- In each call:
- $2$ calls to generate a unique string of length $len(s)+1$ (in the worst case).

- Overall complexity is $O(n^2)$.

Space complexity: $O(n)$.

- The set to store all unique strings uses a space of $O(n)$.
- The maximum length of the call stack will grow to a size of $O(n)$.

## Code

1 | class Solution { |

# Approach 2: Convert binary strings to decimal integers

## Intuition

- We can convert the binary strings to decimal integers and store them in a set. The binary string of any integer that is not a member of this set is the answer.

## Approach

- Convert binary strings to decimal integers and store them in a set
`digits`

. - Search from 0 to $2^n$ (
`n`

is the size of`nums`

):- If a number is not a member of
`digits`

, then convert it to a binary string and return it.

- If a number is not a member of

Pseudocode of this approach:

1 | findDifferentBinaryString(nums): |

## Complexity

Time complexity: $O(2^n)$.

- $n$ iterations to convert binary strings to integers and add them to the set.
- In each iteration:
- Converting a binary string to a decimal digit is $O(n)$.

- At most $2^n$ iterations to find a decimal integer that is not a member of
`digits`

. - Overall complexity is $O(n^2)$.

Space complexity: $O(n)$.

- The maximum size of
`digits`

is $n$.

## Code

1 | class Solution { |