Show problems as
Classic problem #696EasyTwo PointersString

Count Binary Substrings

Real-world version: Paired Stamp Blocks
Tracked in this browser only
Read Count Binary Substrings on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A sorting line marks every item that passes the head with one of two stamps, recorded as the character '0' or '1'. One shift comes back as the string stamps, holding the marks in the order the items went by.

A paired stretch is a run of consecutive positions in the record that is made of two solid blocks: some number of one stamp, immediately followed by the same number of the other stamp. Nothing inside either block may break it.

Return how many paired stretches the record contains. A stretch is identified by where it begins and where it ends, so two stretches that read alike but sit at different places in the record both count, and stretches are allowed to overlap.

Examples

Example 1

Input
stamps = "0011100"
Output
4

The paired stretches are positions 2 to 3 reading 01, positions 1 to 4 reading 0011, positions 5 to 6 reading 10, and positions 4 to 7 reading 1100.

Example 2

Input
stamps = "1110"
Output
1

Only positions 3 to 4, reading 10, split into two solid blocks of equal length.

Example 3

Input
stamps = "000"
Output
0

The record carries one stamp throughout, so no stretch of it holds a block of each stamp.

Constraints

  • 1 <= stamps.length <= 10^5
  • Each character of stamps is either '0' or '1'

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_paired_blocks(stamps: str) -> int:
Java
public int countPairedBlocks(String stamps)

More on the same topics