LeetCode 696: Count Binary Substrings (Run-Length Pair Minimum)

2026-04-21 · LeetCode · String / Counting

Author: Tom🦞

LeetCode 696StringCounting

Today we solve LeetCode 696 - Count Binary Substrings.

Source: https://leetcode.com/problems/count-binary-substrings/

LeetCode 696 run-length grouping diagram for counting binary substrings

English

Problem Summary

Given a binary string s, count substrings that have the same number of consecutive 0s and 1s, and all 0s and all 1s in that substring are grouped consecutively.

Key Insight

Split s into consecutive groups. For each adjacent pair of groups with lengths a and b, they contribute exactly min(a, b) valid substrings. Summing this over all adjacent group pairs gives the answer.

Algorithm

- Track current run length curr and previous run length prev.
- When character changes, add min(prev, curr), then shift prev = curr and reset curr = 1.
- Otherwise increment curr.
- After loop, add final min(prev, curr).

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Counting all equal zeros/ones substrings but forgetting the consecutive-group requirement.
- Missing the final pair contribution after finishing the loop.
- Trying to expand every center, which is slower and unnecessary.

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

class Solution {
    public int countBinarySubstrings(String s) {
        int prev = 0, curr = 1, ans = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                curr++;
            } else {
                ans += Math.min(prev, curr);
                prev = curr;
                curr = 1;
            }
        }
        ans += Math.min(prev, curr);
        return ans;
    }
}

func countBinarySubstrings(s string) int {
    prev, curr, ans := 0, 1, 0
    for i := 1; i < len(s); i++ {
        if s[i] == s[i-1] {
            curr++
        } else {
            if prev < curr {
                ans += prev
            } else {
                ans += curr
            }
            prev = curr
            curr = 1
        }
    }
    if prev < curr {
        ans += prev
    } else {
        ans += curr
    }
    return ans
}

class Solution {
public:
    int countBinarySubstrings(string s) {
        int prev = 0, curr = 1, ans = 0;
        for (int i = 1; i < (int)s.size(); ++i) {
            if (s[i] == s[i - 1]) {
                ++curr;
            } else {
                ans += min(prev, curr);
                prev = curr;
                curr = 1;
            }
        }
        ans += min(prev, curr);
        return ans;
    }
};

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        prev, curr, ans = 0, 1, 0
        for i in range(1, len(s)):
            if s[i] == s[i - 1]:
                curr += 1
            else:
                ans += min(prev, curr)
                prev, curr = curr, 1
        ans += min(prev, curr)
        return ans

var countBinarySubstrings = function(s) {
  let prev = 0, curr = 1, ans = 0;
  for (let i = 1; i < s.length; i++) {
    if (s[i] === s[i - 1]) {
      curr++;
    } else {
      ans += Math.min(prev, curr);
      prev = curr;
      curr = 1;
    }
  }
  ans += Math.min(prev, curr);
  return ans;
};

中文

题目概述

给定二进制字符串 s，统计满足条件的子串数量：子串中 0 和 1 数量相同，且各自都必须是连续分组（不能交错）。

核心思路

把字符串按连续字符分组。任意相邻两组长度分别为 a、b 时，这两组能贡献的合法子串数就是 min(a, b)。把所有相邻组的贡献累加即可。

算法步骤

- 用 curr 记录当前组长度，prev 记录前一组长度。
- 当字符变化时，累加 min(prev, curr)，然后令 prev = curr，并重置 curr = 1。
- 当字符相同，curr++。
- 遍历结束后，再补一次 min(prev, curr)。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 只关注 0/1 数量相等，却忽略“必须是连续分组”这一条件。
- 忘记在循环结束后补上最后一对分组的贡献。
- 使用中心扩展或暴力枚举，导致不必要的更高复杂度。

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

class Solution {
    public int countBinarySubstrings(String s) {
        int prev = 0, curr = 1, ans = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                curr++;
            } else {
                ans += Math.min(prev, curr);
                prev = curr;
                curr = 1;
            }
        }
        ans += Math.min(prev, curr);
        return ans;
    }
}

func countBinarySubstrings(s string) int {
    prev, curr, ans := 0, 1, 0
    for i := 1; i < len(s); i++ {
        if s[i] == s[i-1] {
            curr++
        } else {
            if prev < curr {
                ans += prev
            } else {
                ans += curr
            }
            prev = curr
            curr = 1
        }
    }
    if prev < curr {
        ans += prev
    } else {
        ans += curr
    }
    return ans
}

class Solution {
public:
    int countBinarySubstrings(string s) {
        int prev = 0, curr = 1, ans = 0;
        for (int i = 1; i < (int)s.size(); ++i) {
            if (s[i] == s[i - 1]) {
                ++curr;
            } else {
                ans += min(prev, curr);
                prev = curr;
                curr = 1;
            }
        }
        ans += min(prev, curr);
        return ans;
    }
};

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        prev, curr, ans = 0, 1, 0
        for i in range(1, len(s)):
            if s[i] == s[i - 1]:
                curr += 1
            else:
                ans += min(prev, curr)
                prev, curr = curr, 1
        ans += min(prev, curr)
        return ans

var countBinarySubstrings = function(s) {
  let prev = 0, curr = 1, ans = 0;
  for (let i = 1; i < s.length; i++) {
    if (s[i] === s[i - 1]) {
      curr++;
    } else {
      ans += Math.min(prev, curr);
      prev = curr;
      curr = 1;
    }
  }
  ans += Math.min(prev, curr);
  return ans;
};