Count Binary Substrings

Easy Arrays & Hashing Contribution Technique Original on LeetCode

Count Binary Substrings is a easy arrays & hashing problem solved with the contribution technique pattern. The best approach, optimal (previous and current block only), runs in O(n) time and O(1) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (check every start) up.

Problem

You are given a binary string s. Count the non-empty substrings in which the number of 0s equals the number of 1s and all the 0s are consecutive and all the 1s are consecutive (so the substring looks like 0…01…1 or 1…10…0 with equal halves).

Substrings at different positions are counted separately, even if they contain the same text.

Examples

Example 1

Input
s = "00110"
Output
3
Why
The valid substrings are "01", "0011" and "10". The same text at different positions would be counted separately.

Example 2

Input
s = "10101"
Output
4
Why
Each neighbouring pair ("10", "01", "10", "01") qualifies; nothing longer does, because the blocks have length 1.

Example 3

Input
s = "1110"
Output
1
Why
Only the final "10" works; "110" and "1110" have unequal counts.

Constraints

  • 1 <= s.length <= 10^5
  • s[i] is '0' or '1'.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (check every start)O(n²)O(1)
Block lengthsO(n)O(n)
Optimal (previous and current block only)O(n)O(1)

1Brute force (check every start)

TimeO(n²)From each start the run and the check can scan up to n characters (for example "0000011111").
SpaceO(1)Only counters.

A valid substring is k copies of one bit followed by k copies of the other. From each start i, measure the run of s[i] (length a), then check whether the next a characters are all the opposite bit. Each start contributes at most one substring.

  1. For each start i, let a be the length of the run of s[i] beginning at i.
  2. If the a characters right after that run exist and all differ from s[i], count 1.
  3. Sum over all starts.
class Solution {
    public int countBinarySubstrings(String s) {
        int n = s.length(), total = 0;
        for (int i = 0; i < n; i++) {
            int j = i;
            while (j < n && s.charAt(j) == s.charAt(i)) j++;
            int a = j - i;
            if (j + a > n) continue;
            boolean ok = true;
            for (int k = j; k < j + a; k++) {
                if (s.charAt(k) == s.charAt(i)) { ok = false; break; }
            }
            if (ok) total++;
        }
        return total;
    }
}

2Block lengths

TimeO(n)One pass to build the blocks and one over the blocks.
SpaceO(n)Up to n block lengths (alternating string).

Compress the string into the lengths of its blocks of equal characters, e.g. "0011100" becomes [2, 3, 2]. Two neighbouring blocks of lengths a and b produce exactly min(a, b) valid substrings: "01", "0011", … up to the shorter block.

  1. Build the list of block lengths in one pass.
  2. Add min(groups[i - 1], groups[i]) for every i >= 1.
class Solution {
    public int countBinarySubstrings(String s) {
        List<Integer> groups = new ArrayList<>();
        int run = 1;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) run++;
            else { groups.add(run); run = 1; }
        }
        groups.add(run);
        int total = 0;
        for (int i = 1; i < groups.size(); i++) {
            total += Math.min(groups.get(i - 1), groups.get(i));
        }
        return total;
    }
}

3Optimal (previous and current block only)

TimeO(n)A single pass over the string.
SpaceO(1)Two block lengths and a total.

The block-length sum only ever looks at two neighbouring blocks, so keep just the length of the previous block and of the current one. Each time a block ends, add min(prev, cur) and shift.

  1. prev = 0, cur = 1.
  2. For i from 1: if s[i] == s[i - 1], cur++; otherwise add min(prev, cur), then prev = cur and cur = 1.
  3. After the loop add min(prev, cur) for the last boundary.
class Solution {
    public int countBinarySubstrings(String s) {
        int prev = 0, cur = 1, total = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                cur++;
            } else {
                total += Math.min(prev, cur);
                prev = cur;
                cur = 1;
            }
        }
        return total + Math.min(prev, cur);
    }
}

Edge cases to test

  • A single character (answer 0)
  • All characters equal (answer 0)
  • Strictly alternating string (answer n - 1)
  • Two long blocks like "000111" (answer 3)

Hints

Hint 1

In a valid substring all the 0s are together and all the 1s are together, so it spans exactly one boundary between two blocks of equal characters.

Hint 2

Compress the string into block lengths. Two neighbouring blocks of lengths a and b give how many valid substrings?

Hint 3

You only ever need the previous block length and the current one.

FAQ

What is the best time complexity for Count Binary Substrings?

Optimal (previous and current block only) runs in O(n) time and O(1) extra space. A single pass over the string.

Which pattern does Count Binary Substrings use?

It is a arrays & hashing problem that uses the contribution technique pattern. Other problems with the same pattern: Count Unique Characters of All Substrings of a Given String.

Is there a brute force solution for Count Binary Substrings?

Yes. Brute force (check every start) takes O(n²) time and O(1) space. A valid substring is k copies of one bit followed by k copies of the other.

Which edge cases should I test for Count Binary Substrings?

A single character (answer 0); All characters equal (answer 0); Strictly alternating string (answer n - 1); Two long blocks like "000111" (answer 3).