Skip to content

1016. Binary String With Substrings Representing 1 To N 👎

  • Time: $O(|\texttt{s}|)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  bool queryString(string s, int n) {
    if (n > 1511)
      return false;

    for (int i = n; i > n / 2; --i) {
      string binary = bitset<32>(i).to_string();
      binary = binary.substr(binary.find("1"));
      if (s.find(binary) == string::npos)
        return false;
    }

    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
  public boolean queryString(String s, int n) {
    if (n > 1511)
      return false;

    for (int i = n; i > n / 2; --i)
      if (!s.contains(Integer.toBinaryString(i)))
        return false;

    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
  def queryString(self, s: str, n: int) -> bool:
    if n > 1511:
      return False

    for i in range(n, n // 2, -1):
      if format(i, 'b') not in s:
        return False

    return True