Length Five Palindromic Subsequences
HardDynamic Programming · Uber
Given a string message of lowercase letters, count the palindromic subsequences of length exactly 5.
A subsequence is chosen by picking 5 indices i < j < m < p < q and reading message[i] message[j] message[m] message[p] message[q]. It is a palindrome when message[i] == message[q] and message[j] == message[p] (the middle character can be anything).
Different choices of indices count separately, even if they spell the same string.
Since the answer can be large, return it modulo 10^9 + 7.
Example 1
- Input:
- message = "racecars"
- Output:
- 5
- Explanation
- The outer
rs at indices 0 and 6 with theas at 1 and 5 can take any of the three middle letters (c,e,c), giving 3. Two more come fromr c e c r(indices 0, 2, 3, 4, 6) anda c e c a(indices 1 to 5), for 5 in total.
Example 2
- Input:
- message = "aaaaaa"
- Output:
- 6
- Explanation
- Every choice of 5 indices out of 6 is a palindrome, and there are 6 such choices.
Example 3
- Input:
- message = "abcde"
- Output:
- 0
- Explanation
- The only length-5 subsequence is the whole string, and
"abcde"is not a palindrome.
Constraints
1 <= message.length <= 3000messageconsists of lowercase English letters