Show problems as
Classic problem #647MediumTwo PointersStringDynamic Programming

Palindromic Substrings

Real-world version: Reversible Tape Stretches
Tracked in this browser only
Read Palindromic Substrings on LeetCode(opens in a new tab)

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

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 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_reversible_stretches(tape: str) -> int:
Java
public int countReversibleStretches(String tape)

More on the same topics