What is the time complexity of LeetCode 1016. Binary String With Substrings Representing 1 To N?

The Python solution on this page runs in O(m^2 \times \log m).

What is the space complexity of LeetCode 1016. Binary String With Substrings Representing 1 To N?

The Python solution on this page uses O(\log n), where m is the length of string s and n is the positive integer given in the problem auxiliary space.

Binary String With Substrings Representing 1 To N — LeetCode 1016 Python Solution

MediumBit ManipulationHash TableStringSliding Window

Problem: #1016
Pattern: Sliding Window
Reading time: 2 min
Source: leetcode.com

The problem

Given a binary string s and a positive integer n, return true if the binary representation of all the integers in the range [1, n] are substrings of s, or false otherwise. A substring is a contiguous sequence of characters within a string.

Example

Input: s = "0110", n = 3
Output: true

Python solution

Python

class Solution:
    def queryString(self, s: str, n: int) -> bool:
        if n > 1000:
            return False
        return all(bin(i)[2:] in s for i in range(n, n // 2, -1))

Complexity

Measure	Complexity
Time	O(m^2 \times \log m)
Space	O(\log n), where m is the length of string s and n is the positive integer given in the problem auxiliary

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 1016. Binary String With Substrings Representing 1 To N is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1016. Binary String With Substrings Representing 1 To N?: LeetCode 1016. Binary String With Substrings Representing 1 To N is rated Medium on LeetCode.
What is the time complexity of LeetCode 1016. Binary String With Substrings Representing 1 To N?: The Python solution on this page runs in O(m^2 \times \log m).
What is the space complexity of LeetCode 1016. Binary String With Substrings Representing 1 To N?: The Python solution on this page uses O(\log n), where m is the length of string s and n is the positive integer given in the problem auxiliary space.
What topics does LeetCode 1016. Binary String With Substrings Representing 1 To N cover?: LeetCode 1016. Binary String With Substrings Representing 1 To N is tagged Bit Manipulation, Hash Table, String and Sliding Window on LeetCode.