LeetCode 1016. Binary String With Substrings Representing 1 To N

Description

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 <= 109

Explanation

Convert numbers to binary string and check if it is a substring in the string.

Python Solution

class Solution:
    def queryString(self, s: str, n: int) -> bool:
        
        for i in range(1, n + 1):
            i_bin = bin(i)[2:]
            
            if i_bin not in s:
                return False
            
        return True
  • Time Complexity: O(N).
  • Space Complexity: O(1).

Leave a Reply

Your email address will not be published.