# ---
# title: 1016. Binary String With Substrings Representing 1 To N
# id: problem1016
# author: Indigo
# date: 2021-01-30
# difficulty: Medium
# categories: String
# link: <https://leetcode.com/problems/binary-string-with-substrings-representing-1-to-n/description/>
# hidden: true
# ---
# 
# 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`
# 
# 
## @lc code=start
using LeetCode

function query_string(S::String, N::Int)
    m = (N >> 1) + 1
    for i in m:N
        s_bit = join(reverse!(digits(i; base=2)))
        !occursin(s_bit, S) && return false
    end
    return true
end
## @lc code=end
