# 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`

``````class Solution {
public:
bool queryString(string S, int N) {
for (int i = N; i > 0; --i) {
string b = bitset<32>(i).to_string();
if (S.find(b.substr(b.find("1"))) == string::npos) return false;
}
return true;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1016

https://leetcode.com/problems/binary-string-with-substrings-representing-1-to-n/

https://leetcode.com/problems/binary-string-with-substrings-representing-1-to-n/discuss/260847/JavaC%2B%2BPython-O(S)

https://leetcode.com/problems/binary-string-with-substrings-representing-1-to-n/discuss/260882/C%2B%2B-O(S-log-N)-vs.-O(N-*-(S-%2B-log-N))

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation