Binary string with substrings representing 1 to n

Hash Table String Bit Manipulation Sliding Window

58.4% acceptance

Feb 25, 2026

386

540

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn query_string(s: String, n: i32) -> bool {
    if n > 1023 { return false; } // s.len()<=1000, can only represent up to 2^1000-1, but n up to 10^9
    for i in 1..=n {
      let bin = format!("{:b}", i);
      if !s.contains(&bin as &str) { return false; }
    }
    true
  }
}