0084MediumTwo PointersStringDynamic Programming

Reversible Tape Stretches

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 label printer has run off a tape of lowercase letters, handed to you as the string tape. Quality control wants to know how much of the tape reads the same whichever way you feed it into the reader.

A stretch is one or more neighbouring letters of the tape, pinned down by where it starts and where it ends. A stretch is reversible when its letters spell out the same thing read right to left as they do read left to right. A stretch of a single letter is reversible.

Return how many reversible stretches the tape holds. Stretches that cover different positions count separately, even when they spell the same letters, so the tape "dd" holds three: each d on its own, plus the pair.

Examples

Example 1

Input: tape = "dvd"
Output: 4

The three single letters are reversible, and so is the whole tape.

Example 2

Input: tape = "pqqp"
Output: 6

Four single letters, then `qq`, then the whole tape, and nothing else reads the same both ways.

Example 3

Input: tape = "wxyz"
Output: 4

No two neighbouring letters match, so only the four single letters are reversible.

Constraints

1 <= tape.length <= 1000
tape holds lowercase English letters only

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_reversible_stretches(tape: str) -> int:

Java

public int countReversibleStretches(String tape)

The intended approach

Time O(n^2)Space O(1)

Every reversible stretch grows outwards from its middle, and the middle is either one letter or the seam between two neighbouring letters. Anchor each of those 2n - 1 middles in turn and push a pair of indices apart while the letters they land on agree, counting one stretch per successful step. Nothing but the two indices is stored.

Pythonentry point: count_reversible_stretches

def count_reversible_stretches(tape):
    n = len(tape)
    total = 0
    for centre in range(n):
        lo, hi = centre, centre
        while lo >= 0 and hi < n and tape[lo] == tape[hi]:
            total += 1
            lo -= 1
            hi += 1
        lo, hi = centre, centre + 1
        while lo >= 0 and hi < n and tape[lo] == tape[hi]:
            total += 1
            lo -= 1
            hi += 1
    return total

The obvious version

Cut out every start and end pair and compare the slice with its own reversal. O(n^3) with no notion of a middle.

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_reversible_stretches(tape):
    n = len(tape)
    total = 0
    for start in range(n):
        for stop in range(start + 1, n + 1):
            chunk = tape[start:stop]
            if chunk == chunk[::-1]:
                total += 1
    return total

How this problem was checked

Reference solution executed against 11 test cases — 11 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