How hard is LeetCode 696. Count Binary Substrings?

LeetCode 696. Count Binary Substrings is rated Easy on LeetCode.

What is the time complexity of LeetCode 696. Count Binary Substrings?

The Python solution on this page runs in O(n) (after optional sort O(n log n)).

What is the space complexity of LeetCode 696. Count Binary Substrings?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 696. Count Binary Substrings cover?

LeetCode 696. Count Binary Substrings is tagged Two Pointers and String on LeetCode.

Count Binary Substrings — LeetCode 696 Python Solution

EasyTwo PointersString

Problem: #696
Pattern: Two Pointers
Reading time: 3 min
Source: leetcode.com

The problem

Given a binary string s, return the number of non-empty substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur.

Example

Input: s = "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".

Python solution

Python

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        i, n = 0, len(s)
        t = []
        while i < n:
            cnt = 1
            while i + 1 < n and s[i + 1] == s[i]:
                cnt += 1
                i += 1
            t.append(cnt)
            i += 1
        ans = 0
        for i in range(1, len(t)):
            ans += min(t[i - 1], t[i])
        return ans

Complexity

Measure	Complexity
Time	O(n) (after optional sort O(n log n))
Space	O(1) auxiliary

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 696. Count Binary Substrings is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Two Pointers.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 696. Count Binary Substrings?: LeetCode 696. Count Binary Substrings is rated Easy on LeetCode.
What is the time complexity of LeetCode 696. Count Binary Substrings?: The Python solution on this page runs in O(n) (after optional sort O(n log n)).
What is the space complexity of LeetCode 696. Count Binary Substrings?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 696. Count Binary Substrings cover?: LeetCode 696. Count Binary Substrings is tagged Two Pointers and String on LeetCode.