Show problems as
Classic problem #2484HardStringDynamic Programming

Count Palindromic Subsequences

Real-world version: Five-Digit Mirror Picks
Tracked in this browser only
Read Count Palindromic Subsequences on LeetCode(opens in a new tab)

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

A cloakroom prints a strip of digits on every ticket. The strip is given as the string strip, made up of digit characters.

A pick marks five positions of the strip and reads the digits sitting there from the lowest marked position to the highest. A pick is a mirror pick when the five digits it reads are unchanged by reading them the other way round, that is, when the first digit equals the fifth and the second equals the fourth. The digit in the middle is under no such condition.

Two picks count as different when the sets of positions they mark are different, even if both read the same five digits. Return the number of mirror picks as a remainder modulo 10^9 + 7.

Examples

Example 1

Input
strip = "48284"
Output
1

The strip has exactly five positions, so there is one pick, and the digits 4, 8, 2, 8, 4 it reads are unchanged the other way round.

Example 2

Input
strip = "222222"
Output
6

Any five of the six positions read 22222, and there are six ways to leave one position unmarked, so six different position sets qualify.

Example 3

Input
strip = "1027301"
Output
3

Positions 0, 1, 5 and 6 carry 1, 0, 0 and 1, and marking any one of positions 2, 3 or 4 alongside them reads 10201, 10701 and 10301.

Constraints

  • 1 <= strip.length <= 10^4
  • strip consists of digit characters only
  • Return the count modulo 10^9 + 7

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_mirror_picks(strip: str) -> int:
Java
public int countMirrorPicks(String strip)

More on the same topics