Problem

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]_aresubstrings of _s , orfalse otherwise.

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

Examples

Example 1

1
2

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

Example 2

1
2

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

Constraints

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

Solution

Method 1 – Sliding Window and Set

Intuition

To check if all binary representations of numbers from 1 to n are substrings of s, we can generate all such binary strings and check if each is present in s. To optimize, we can use a set to store all substrings of s of relevant lengths and compare.

Approach

  1. For each k from 1 to n, get its binary representation as a string.
  2. For each possible length (from the length of bin(1) to bin(n)), collect all substrings of s of that length into a set.
  3. For each k, check if its binary string is in the set of substrings.
  4. If all are present, return true; otherwise, return false.

Code

 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) {
        for (int k = n; k >= 1; --k) {
            string t;
            int x = k;
            while (x) {
                t += (x % 2) + '0';
                x /= 2;
            }
            reverse(t.begin(), t.end());
            if (s.find(t) == string::npos) return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9

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

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

class Solution {
    fun queryString(s: String, n: Int): Boolean {
        for (k in n downTo 1) {
            val t = Integer.toBinaryString(k)
            if (!s.contains(t)) return false
        }
        return true
    }
}
1
2
3
4
5
6

class Solution:
    def queryString(self, s: str, n: int) -> bool:
        for k in range(n, 0, -1):
            if bin(k)[2:] not in s:
                return False
        return True
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn query_string(s: String, n: i32) -> bool {
        for k in (1..=n).rev() {
            let t = format!("{:b}", k);
            if !s.contains(&t) {
                return false;
            }
        }
        true
    }
}

Complexity

  • ⏰ Time complexity: O(nL) where L is the max length of binary strings up to n, and each substring search is O(|s|).
  • 🧺 Space complexity: O(1) if not storing substrings, or up to O(|s|) if using a set for optimization.