Problem of The Day: Count Binary Substrings

5 min read 1166 words

Problem Statement

leetcode problem link

Solution [Accepted]

Expand the window to the left and right of the current index.

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        res = 0
        N = len(s)
        for i in range(1, N):
            l, r = i - 1, i
            leftChar = s[l]
            rightChar = s[r]
            while l >= 0 and r < N and s[l] != s[r] and s[l] == leftChar and s[r] == rightChar:
                res += 1
                l -= 1
                r += 1

        return res

public class Solution {
    public int CountBinarySubstrings(string s) {
        int res = 0;
        int N = s.Length;
        for (int i = 1; i < N; i++) {
            int l = i - 1, r = i;
            char leftChar = s[l];
            char rightChar = s[r];
            while (l >= 0 && r < N && s[l] != s[r] && s[l] == leftChar && s[r] == rightChar) {
                res++;
                l--;
                r++;
            }
        }
        return res;
    }
}

• time: O(n^2)
• space: O(1)

Editorial

Approach #1: Group By Character [Accepted]

How it works:

The core intuition is that any valid substring must be formed at the boundary where characters change (e.g., from 0 to 1). If you have a block of X identical characters followed by a block of Y different identical characters, you can always form min(X, Y) valid substrings by taking characters from the boundary and expanding outwards.

Example: s = "000111100"

1. Grouping: Count consecutive identical characters.
   • "000" → 3
   • "1111" → 4
   • "00" → 2
   • Result: groups = [3, 4, 2]
2. Counting: Look at adjacent groups.
   • Between 3 zeros and 4 ones: min(3, 4) = 3 substrings ("01", "0011", "000111")
   • Between 4 ones and 2 zeros: min(4, 2) = 2 substrings ("10", "1100")
3. Total: 3 + 2 = 5

class Solution(object):
    def countBinarySubstrings(self, s):
        groups = [1]
        for i in xrange(1, len(s)):
            if s[i-1] != s[i]:
                groups.append(1)
            else:
                groups[-1] += 1

        ans = 0
        for i in range(1, len(groups)):
            ans += min(groups[i-1], groups[i])
        return ans

public class Solution {
    public int CountBinarySubstrings(string s) {
        List<int> groups = new List<int> { 1 };
        for (int i = 1; i < s.Length; i++) {
            if (s[i - 1] != s[i]) {
                groups.Add(1);
            } else {
                groups[groups.Count - 1]++;
            }
        }

        int ans = 0;
        for (int i = 1; i < groups.Count; i++) {
            ans += Math.Min(groups[i - 1], groups[i]);
        }
        return ans;
    }
}

Approach #2: Linear Scan [Accepted]

class Solution(object):
    def countBinarySubstrings(self, s):
        ans, prev, cur = 0, 0, 1
        for i in range(1, len(s)):
            if s[i-1] != s[i]:
                ans += min(prev, cur)
                prev, cur = cur, 1
            else:
                cur += 1

        return ans + min(prev, cur)

public class Solution {
    public int CountBinarySubstrings(string s) {
        int ans = 0, prev = 0, cur = 1;
        for (int i = 1; i < s.Length; i++) {
            if (s[i - 1] != s[i]) {
                ans += Math.Min(prev, cur);
                prev = cur;
                cur = 1;
            } else {
                cur++;
            }
        }
        return ans + Math.Min(prev, cur);
    }
}