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

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