2484

2484. Count Palindromic Subsequences (Hard)

Given a string of digits s, return the number of palindromic subsequences of s having length 5. Since the answer may be very large, return it modulo 109 + 7.

Note:

• A string is palindromic if it reads the same forward and backward.
• A subsequence is a string that can be derived from another string by deleting some or no characters 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".

 

Constraints:

• 1 <= s.length <= 104
• s consists of digits.

Companies: Goldman Sachs, Atlassian

Related Topics:
String, Dynamic Programming

Similar Questions:

• Arithmetic Slices II - Subsequence (Hard)
• Count Different Palindromic Subsequences (Hard)
• Unique Length-3 Palindromic Subsequences (Medium)

Solution 1. DP

Let left[a][b][i] be the number of ab subsequences in s[0..i], right[a][b][i] be the number of ba subsequences in s[i..(N-1)], where 0 <= a, b <= 9, 0 <= i < N.

The answer is SUM( left[a][b][i-1] * right[a][b][i+1] | 0 <= a, b <= 9 and 0 <= i < N )

We can use the following to compute left[a][b][i].

left[a][b][i] = left[a][b][i-1] + (s[i] == b ? ca[i-1] : 0)

where ca[i] is the number of character as in A[0..i].

// OJ: https://leetcode.com/problems/count-palindromic-subsequences
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int countPalindromes(string s) {
        long N = s.size(), mod = 1e9 + 7, ans = 0;
        vector<vector<vector<long>>> left(10, vector<vector<long>>(10, vector<long>(N))), right(10, vector<vector<long>>(10, vector<long>(N)));
        for (int a = 0; a <= 9; ++a) {
            for (int b = 0; b <= 9; ++b) {
                long ca = 0, cnt = 0;
                for (int i = 0; i < N; ++i) {
                    if (s[i] - '0' == b) cnt = (cnt + ca) % mod;
                    left[a][b][i] = cnt;
                    ca += s[i] - '0' == a;
                }
                ca = 0, cnt = 0;
                for (int i = N - 1; i >= 0; --i) {
                    if (s[i] - '0' == b) cnt = (cnt + ca) % mod;
                    right[a][b][i] = cnt;
                    ca += s[i] - '0' == a;
                }
            }
        }
        for (int i = 2; i < N - 2; ++i) {
            for (int a = 0; a <= 9; ++a) {
                for (int b = 0; b <= 9; ++b) {
                    ans = (ans + left[a][b][i - 1] * right[a][b][i + 1] % mod) % mod;
                }
            }
        }
        return ans;
    }
};