#2484
Count Palindromic Subsequences
master · 1675 · lc hard +32 · verified · 41% accepted · 609 likes · top 21%
Description
Given a digit string s, count the number of distinct palindromic subsequences of length exactly 5 and return the result modulo 109 + 7.
A string is palindromic if it reads the same forwards and backwards. A subsequence is formed by deleting zero or more characters from s without changing the order of the remaining characters.
Example 1:
Input: s = "103301"
Output: 2
Explanation:
There are 6 possible subsequences of length 5: "10330","10331","10301","10301","13301","03301".
Two of them (both equal to "10301") are palindromic.
Example 2:
Input: s = "0000000"
Output: 21
Explanation: All 21 subsequences are "00000", which is palindromic.
Example 3:
Input: s = "9999900000"
Output: 2
Explanation: The only two palindromic subsequences are "99999" and "00000".
Code
1
2
3