0252EasyTwo PointersString

Paired Stamp Blocks

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def count_paired_blocks(stamps: str) -> int:

Java

public int countPairedBlocks(String stamps)

The intended approach

Time O(n)Space O(1)

Walk the record once while tracking the length of the block being read and the length of the block just before it. Every time the block being read is no longer than the one before it, the position just reached closes exactly one more paired stretch, so add one. A change of stamp retires the current length into the previous one and restarts the count at one.

Pythonentry point: count_paired_blocks

def count_paired_blocks(stamps):
    total = 0
    previous_run = 0
    current_run = 1
    for i in range(1, len(stamps)):
        if stamps[i] == stamps[i - 1]:
            current_run += 1
        else:
            previous_run = current_run
            current_run = 1
        if previous_run >= current_run:
            total += 1
    return total

The obvious version

Cut out every stretch of even length, split it down the middle and check that each half is solid and that the two halves carry different stamps. O(n^3).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_count_paired_blocks(stamps):
    n = len(stamps)
    total = 0
    for start in range(n):
        for stop in range(start + 2, n + 1, 2):
            piece = stamps[start:stop]
            half = len(piece) // 2
            front = piece[:half]
            back = piece[half:]
            if front != front[0] * half:
                continue
            if back != back[0] * half:
                continue
            if front[0] == back[0]:
                continue
            total += 1
    return total

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in