Skip to content

1016. Binary String With Substrings Representing 1 To N

Description

Given a binary string s and a positive integer n, return true if the binary representation of all the integers in the range [1, n] are substrings of s, or false otherwise.

A substring is a contiguous sequence of characters within a string.

 

Example 1:

Input: s = "0110", n = 3
Output: true

Example 2:

Input: s = "0110", n = 4
Output: false

 

Constraints:

  • 1 <= s.length <= 1000
  • s[i] is either '0' or '1'.
  • 1 <= n <= 109

Solutions

Solution 1: Brain Teaser

Thinking

\(n\) can be \(10^9\), so testing every binary representation in \([1,n]\) is impossible. \(s\) has length at most \(1000\), so it cannot cover more than a thousand distinct values and \(n>1000\) is immediately false.

If the binary form of \(x\) occurs in \(s\), then \(\lfloor x/2\rfloor\) (drop the last bit) occurs as well. It is enough to check the upper half \([\lfloor n/2\rfloor+1,n]\).

Under \(n\le 1000\) we test those integers with ordinary substring search.

We observe that the length of string \(s\) does not exceed \(1000\), so string \(s\) can represent at most \(1000\) binary integers. Therefore, if \(n \gt 1000\), then \(s\) definitely cannot represent the binary representation of all integers in the range \([1,.. n]\).

Additionally, for an integer \(x\), if the binary representation of \(x\) is a substring of \(s\), then the binary representation of \(\lfloor x / 2 \rfloor\) is also a substring of \(s\). Therefore, we only need to check whether the binary representations of integers in the range \([\lfloor n / 2 \rfloor + 1,.. n]\) are substrings of \(s\).

The time complexity is \(O(m^2 \times \log m)\) and the space complexity is \(O(\log n)\), where \(m\) is the length of string \(s\) and \(n\) is the positive integer given in the problem.

1
2
3
4
5
class Solution:
    def queryString(self, s: str, n: int) -> bool:
        if n > 1000:
            return False
        return all(bin(i)[2:] in s for i in range(n, n // 2, -1))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public boolean queryString(String s, int n) {
        if (n > 1000) {
            return false;
        }
        for (int i = n; i > n / 2; i--) {
            if (!s.contains(Integer.toBinaryString(i))) {
                return false;
            }
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    bool queryString(string s, int n) {
        if (n > 1000) {
            return false;
        }
        for (int i = n; i > n / 2; --i) {
            string b = bitset<32>(i).to_string();
            b = b.substr(b.find_first_not_of('0'));
            if (s.find(b) == string::npos) {
                return false;
            }
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func queryString(s string, n int) bool {
    if n > 1000 {
        return false
    }
    for i := n; i > n/2; i-- {
        if !strings.Contains(s, strconv.FormatInt(int64(i), 2)) {
            return false
        }
    }
    return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function queryString(s: string, n: number): boolean {
    if (n > 1000) {
        return false;
    }
    for (let i = n; i > n / 2; --i) {
        if (s.indexOf(i.toString(2)) === -1) {
            return false;
        }
    }
    return true;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func queryString(s string, n int) bool {
    if n > 1000 {
        return false
    }
    for i := n; i > n/2; i-- {
        if !strings.Contains(s, strconv.FormatInt(int64(i), 2)) {
            return false
        }
    }
    return true
}

Comments