LeetCode 1016 - Binary String With Substrings Representing 1 To N

https://leetcode.com/problems/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

X.
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))

We can process the entire string and track all numbers [1..N] that we can build.

OR

We can generate binary string representation for [1..N], and search for it in the string.

Solution 1

• For each non-zero position i in S, gradually build num while num <= N.
• Track each num in seen, increment X for new num.
• Return true if we built all numbers from 1 to N (X == N).

bool queryString(string S, int N, int X = 0) {
  vector<bool> seen(N);
  for (auto i = 0; i < S.size() && X < N; ++i) {
    if (S[i] == '0') continue;
    for (auto j = i, num = 0; num <= N && j < S.size(); ++j) {
      num = (num << 1) + S[j] - '0';
      if (num > 0 && num <= N && !seen[num - 1]) {
        ++X;
        seen[num - 1] = true;
      }
    }
  }
  return X == N;
}

Complexity Analysis

Runtime: O(S log N), where S is the string size. For every position, we analyze log N digits.
Memory: O(N) as we need to track all numbers from 1 to N.

http://www.noteanddata.com/leetcode-1023-Binary-String-With-Substrings-Representing-1-To-N-google-interview-problem-java-solution-note.html

1. 感觉直接遍历N肯定不可行（没想到其实是可以的，因为跳出循环很快， 然后看S， S总共就只有1000位， 那么S的子字符串最多也就10001000, 而实际上， 因为整数最多只有32位二进制， 那么对于每一个index=i， 直接看len=[1,32]， 那么， S的子字符串最多也就100032种可能， 所以如果N > s.length() * 32, 就可以直接return false
2. 然后对每一个index求所有可能的子字符串， 然后放到一个set里面， 然后最后判断这个set是否包含了[1,N]的所有数就好

java题解代码

1. 这里我第一次知道原来32位的二进制的0和1， 不能被全部解析到整数， 比如"10010010011001011010101100110110", 这我就有点晕了, 为什么会出现这样的情况呢？
2. Integer.parseInt(s, base), 字符串不需要补齐到32位
3. 后来看了下其他人很多是采用直接数字操作转化到十进制的， 这个后面再学习一下

时间复杂度
O(32*M), 其中M是S的长度

public boolean queryString(String S, int N) {
    if(N > S.length() * 32) return false;
    Set<Integer> set = new HashSet<>();
    for(int i = 0; i < S.length(); ++i) {
        for(int len = 1; len <= 32; ++len) {
            if(i+len <= S.length()) {
                String sub = S.substring(i, i+len);    
                try {
                    int value = Integer.parseInt(sub, 2);
                    set.add(value);
                }
                catch(Exception e) {
                }
            }
        }
    }
    for(int i = 1; i <= N; ++i) {
        if(!set.contains(i)) {
            return false;
        }
    }
    return true;
}

X.  Brute Force

比较惊讶的是输入数据N是比较大大，可是brute force也可以过。。。可能主要是跳出循环比较快
1. 后来看了下， 直接brute force循环N从大到小也可以过

没想到， 从小到大循环也可以过

https://leetcode.com/problems/binary-string-with-substrings-representing-1-to-n/discuss/261027/The-trick-behind-most-of-the-solutions-Explanation

Actuall looking at most of the solution wich are iterating over N one might feel as if it should give TLE
But the trick here is the fast eleminations
"You cannot fit too many numbers into 1000-character binary string..." (refer to @votrubac 's solution most rated one for better approaches)
We return false as soon as we dont find a perticular no. hence the probability of returning false is very high before the time limit exceeds
Hence it alomost never exceeds limit

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

The construction of S is a NP problem,
it's time consuming to construct a short S.
I notice S.length <= 1000, which is too small to make a big N.

This intuition lead me to the following 1-line python solution,
which can be implemented very fast.

##Explanation:
Check if S contains binary format of N,
If so, continue to check N - 1.

Time Complexity

1. Prove I, check number of substring

Pick two indices, there are at most S^2 substrings,
so S can contains at most S^2 integers
Time complexity upper bound O(S^2)

2. Prove II, Check the continuous digits
   Meanwhile I know the interviewer and my reader won't be satisfied,
   as they want no more "cheat".

Here I have a brief demonstration to give the time complexity an acceptable upper bound.

Have a look at the number 1001 ~ 2000 and their values in binary.

1001 0b1111101001
1002 0b1111101010
1003 0b1111101011
...
1997 0b11111001101
1998 0b11111001110
1999 0b11111001111
2000 0b11111010000

The number 1001 ~ 2000 have 1000 different continuous 10 digits.
The string of length S has at most S - 9 different continuous 10 digits.
So S <= 1000, N <= 2000.

So S * 2 is a upper bound for N.
If N > S * 2, we can return false directly.

It's the same to prove with the numbers 512 ~ 1511, or even smaller range.

Time complexity upper bound O(S)

    public boolean queryString(String S, int N) {
        for (int i = N; i > N / 2; --i)
            if (!S.contains(Integer.toBinaryString(i)))
                return false;
        return true;
    }

X. https://leetcode.com/problems/binary-string-with-substrings-representing-1-to-n/discuss/260907/easy-Java-solution

    public boolean queryString(String S, int N) {
        for(int i =1; i<=N; i++){
            String b = Integer.toBinaryString(i);
            if(!S.contains(b))return false;
        }
        return true;
    }

Small Improvisation: If we observe the binary patterns, we only need to search for the 2nd power of two value, starting from N. Ex: if N=19, we need to search 19 to 8, remaining will be always be there.

https://www.acwing.com/solution/LeetCode/content/1251/

给定一个二进制字符串 S（一个仅由若干 ‘0’ 和 ‘1’ 构成的字符串）和一个正整数 N，如果对于从 1 到 N 的每个整数 X，其二进制表示都是 S 的子串，就返回 true，否则返回 false。

样例

输入：S = "0110", N = 3
输出：true

输入：S = "0110", N = 4
输出：false




(子串枚举) $O(S.length)$

• 直接枚举 S 的长度不超过 30 的子串，如果子串构成了 1 到 N 中的数字，则加到一个集合中，最后判断集合的大小是否等于 N