1016. Binary String With Substrings Representing 1 To N

Given a binary string S (a string consisting only of '0' and '1's) and a positive integer N, return true if and only if for every integer X from 1 to N, the binary representation of X is a substring of S.

 

Example 1:

Input: S = "0110", N = 3
Output: true

Example 2:

Input: S = "0110", N = 4
Output: false

 

Note:

  1. 1 <= S.length <= 1000
  2. 1 <= N <= 10^9

Rust Solution

struct Solution;

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

#[test]
fn test() {
    let s = "0110".to_string();
    let n = 3;
    let res = true;
    assert_eq!(Solution::query_string(s, n), res);
    let s = "0110".to_string();
    let n = 4;
    let res = false;
    assert_eq!(Solution::query_string(s, n), res);
}

Having problems with this solution? Click here to submit an issue on github.