0265HardStringDynamic Programming

Five-Digit Mirror Picks

Tracked in this browser only

Trains the technique from

LeetCode 2484Count Palindromic Subsequences

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 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 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_mirror_picks(strip: str) -> int:

Java

public int countMirrorPicks(String strip)

The intended approach

Time O(100 * n)Space O(n) for the digit values rebuilt from the strip; the two pair tables and the two digit counters are a fixed 10 by 10 and 10 each

Settle the middle position first and count the two sides apart. A mirror pick with middle `mid` is a pair of digits taken in order as `(first, second)` from the part before `mid`, matched with the same pair taken in order as `(second, first)` from the part after `mid`, so the picks with that middle number `sum(left_pairs[first][second] * right_pairs[second][first])` over all 100 digit pairs. Both tables are carried along as the middle slides rightwards: the position the middle leaves behind joins the left part, which extends `left_pairs` using the ten running left digit counts, and the position the middle is about to occupy leaves the right part, which undoes exactly the pairs that started there. Ten digits keep each table at a fixed 10 by 10, so the sweep costs a constant per position of the strip.

Pythonentry point: count_mirror_picks

def count_mirror_picks(strip):
    limit = 10 ** 9 + 7
    n = len(strip)
    if n < 5:
        return 0
    digits = [ord(ch) - 48 for ch in strip]
    left_count = [0] * 10
    left_pairs = [[0] * 10 for _ in range(10)]
    right_count = [0] * 10
    right_pairs = [[0] * 10 for _ in range(10)]
    for i in range(n - 1, 2, -1):
        row = right_pairs[digits[i]]
        for value in range(10):
            row[value] += right_count[value]
        right_count[digits[i]] += 1
    for i in range(2):
        for value in range(10):
            left_pairs[value][digits[i]] += left_count[value]
        left_count[digits[i]] += 1
    total = 0
    for mid in range(2, n - 2):
        for first in range(10):
            row = left_pairs[first]
            for second in range(10):
                if row[second]:
                    total += row[second] * right_pairs[second][first]
        total %= limit
        if mid + 1 <= n - 3:
            entering = digits[mid]
            for value in range(10):
                left_pairs[value][entering] += left_count[value]
            left_count[entering] += 1
            leaving = digits[mid + 1]
            row = right_pairs[leaving]
            for value in range(10):
                row[value] -= right_count[value] - (1 if value == leaving else 0)
            right_count[leaving] -= 1
    return total % limit

The obvious version

Enumerate every choice of five positions and keep the ones whose digits mirror. O(n^5).

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_mirror_picks(strip):
    from itertools import combinations
    limit = 10 ** 9 + 7
    total = 0
    for spots in combinations(range(len(strip)), 5):
        a, b, c, d, e = spots
        if strip[a] == strip[e] and strip[b] == strip[d]:
            total += 1
    return total % limit

How this problem was checked

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