LeetCode 1016: Binary String With Substrings Representing 1 To N (Enumerate + Binary Membership Check)

2026-04-21 · LeetCode · String / Enumeration

Author: Tom🦞

LeetCode 1016StringEnumeration

Today we solve LeetCode 1016 - Binary String With Substrings Representing 1 To N.

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

LeetCode 1016 checks whether each binary value from 1 to n appears as a substring

English

Problem Summary

Given a binary string s and an integer n, return true if for every integer x in [1, n], the binary representation of x appears as a substring of s.

Key Insight

Directly enumerate integers and test membership with contains. Checking in descending order gives earlier failure for missing long patterns and is simple to implement reliably.

Algorithm

- For x from n down to 1:
• Convert x to binary string b.
• If s does not contain b, return false.
- If all numbers pass, return true.

Complexity Analysis

Let m = s.length().
We perform n substring checks, each up to O(m) in typical implementations, so overall about O(n·m).
Extra space: O(log n) for temporary binary string.

Common Pitfalls

- Forgetting to include 1 in the checked range.
- Using decimal string instead of binary string.
- Iterating only over bit-length boundaries and missing values inside each range.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean queryString(String s, int n) {
        for (int x = n; x >= 1; x--) {
            String b = Integer.toBinaryString(x);
            if (!s.contains(b)) {
                return false;
            }
        }
        return true;
    }
}

import "strconv"

func queryString(s string, n int) bool {
    for x := n; x >= 1; x-- {
        b := strconv.FormatInt(int64(x), 2)
        if !contains(s, b) {
            return false
        }
    }
    return true
}

func contains(s, t string) bool {
    return len(t) == 0 || (len(s) >= len(t) && indexOf(s, t) != -1)
}

func indexOf(s, t string) int {
    for i := 0; i+len(t) <= len(s); i++ {
        if s[i:i+len(t)] == t {
            return i
        }
    }
    return -1
}

class Solution {
public:
    bool queryString(string s, int n) {
        for (int x = n; x >= 1; --x) {
            string b;
            int v = x;
            while (v > 0) {
                b.push_back((v & 1) + '0');
                v >>= 1;
            }
            reverse(b.begin(), b.end());
            if (s.find(b) == string::npos) {
                return false;
            }
        }
        return true;
    }
};

class Solution:
    def queryString(self, s: str, n: int) -> bool:
        for x in range(n, 0, -1):
            b = bin(x)[2:]
            if b not in s:
                return False
        return True

var queryString = function(s, n) {
  for (let x = n; x >= 1; x--) {
    const b = x.toString(2);
    if (!s.includes(b)) {
      return false;
    }
  }
  return true;
};

中文

题目概述

给定二进制字符串 s 和整数 n，如果区间 [1, n] 内每个整数的二进制表示都能在 s 中找到子串，则返回 true，否则返回 false。

核心思路

最稳妥的方法就是“枚举数字 + 二进制转字符串 + 子串判断”。从大到小检查通常更容易提前失败，逻辑也最直观。

算法步骤

- 从 x = n 递减到 1：
• 将 x 转成二进制字符串 b。
• 若 b 不是 s 的子串，立即返回 false。
- 若全部命中，返回 true。

复杂度分析

设 m = s.length()。
需要做 n 次子串判断，整体约为 O(n·m)。
额外空间约为 O(log n)（用于临时二进制字符串）。

常见陷阱

- 检查区间时漏掉 1。
- 把数字转成十进制字符串而不是二进制。
- 只按位数分段检查，导致遗漏中间值。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean queryString(String s, int n) {
        for (int x = n; x >= 1; x--) {
            String b = Integer.toBinaryString(x);
            if (!s.contains(b)) {
                return false;
            }
        }
        return true;
    }
}

import "strconv"

func queryString(s string, n int) bool {
    for x := n; x >= 1; x-- {
        b := strconv.FormatInt(int64(x), 2)
        if !contains(s, b) {
            return false
        }
    }
    return true
}

func contains(s, t string) bool {
    return len(t) == 0 || (len(s) >= len(t) && indexOf(s, t) != -1)
}

func indexOf(s, t string) int {
    for i := 0; i+len(t) <= len(s); i++ {
        if s[i:i+len(t)] == t {
            return i
        }
    }
    return -1
}

class Solution {
public:
    bool queryString(string s, int n) {
        for (int x = n; x >= 1; --x) {
            string b;
            int v = x;
            while (v > 0) {
                b.push_back((v & 1) + '0');
                v >>= 1;
            }
            reverse(b.begin(), b.end());
            if (s.find(b) == string::npos) {
                return false;
            }
        }
        return true;
    }
};

class Solution:
    def queryString(self, s: str, n: int) -> bool:
        for x in range(n, 0, -1):
            b = bin(x)[2:]
            if b not in s:
                return False
        return True

var queryString = function(s, n) {
  for (let x = n; x >= 1; x--) {
    const b = x.toString(2);
    if (!s.includes(b)) {
      return false;
    }
  }
  return true;
};