Five-Digit Palindromes in a Digit String

Hard

You get a string digits made of digits. Deleting some of its characters while keeping the rest in order gives a subsequence. Count the ways to choose a subsequence of **length 5** that reads the same forwards and backwards. Two ways are different if they use different sets of positions, even when the resulting strings are equal. The answer can be large, so return it modulo 10⁹ + 7.

Example 1

digits='123321' → 2

Only "12321" works, and it can be picked in two ways, using either of the two 3s.

Example 2

digits='000000' → 6

Any five of the six positions give "00000": 6 ways in total.

Example 3

digits='5678' → 0

Constraints

1 ≤ len(digits) ≤ 10⁴
digits contains only the digits 0–9

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming

Similar problems

Pattern With Dot and Star Hard Longest Balanced Bracket Stretch Hard Does the Text Fit the Pattern Hard Shuffle by Cutting and Swapping Hard Ways to Cross Out Hard

Input

digits='123321'

Expected

Run checks the first 3 tests in your browser. Submit checks all 152 tests on the server, hidden ones included.