Problem

Given a string of digits s, return the number ofpalindromic subsequences of s having length5. Since the answer may be very large, return it modulo 10^9 + 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.

Examples

Example 1

1
2
3
4
5

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

1
2
3

Input: s = "0000000"
Output: 21
Explanation: All 21 subsequences are "00000", which is palindromic.

Example 3

1
2
3

Input: s = "9999900000"
Output: 2
Explanation: The only two palindromic subsequences are "99999" and "00000".

Constraints

  • 1 <= s.length <= 10^4
  • s consists of digits.

Solution

Method 1 – Prefix and Suffix Counting (Dynamic Programming)

Intuition

A palindromic subsequence of length 5 must have the form “abcba”. We can fix the middle character and count the number of ways to choose the first two and last two characters such that they are the same in reverse order. We use prefix and suffix counts for all pairs of digits.

Approach

  1. For each position, precompute prefix counts of all digit pairs (for the first two characters).
  2. For each position, precompute suffix counts of all digit pairs (for the last two characters).
  3. For each possible middle character, for each split, multiply the number of ways to pick a pair before and after the middle.
  4. Sum over all possible pairs and positions.
  5. Return the answer modulo 10^9+7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    int countPalindromes(string s) {
        int n = s.size(), mod = 1e9+7, ans = 0;
        vector<vector<int>> pre(10, vector<int>(10)), suf(10, vector<int>(10));
        vector<int> cnt1(10), cnt2(10);
        for (int i = 0; i < n; ++i) {
            int d = s[i] - '0';
            for (int x = 0; x < 10; ++x) pre[x][d] += cnt1[x];
            cnt1[d]++;
        }
        for (int i = n-1; i >= 0; --i) {
            int d = s[i] - '0';
            for (int x = 0; x < 10; ++x) suf[d][x] += cnt2[x];
            cnt2[d]++;
        }
        for (int i = 2; i < n-2; ++i) {
            for (int a = 0; a < 10; ++a) {
                for (int b = 0; b < 10; ++b) {
                    ans = (ans + pre[a][b] * suf[b][a]) % mod;
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func countPalindromes(s string) int {
    n, mod, ans := len(s), int(1e9+7), 0
    pre := make([][]int, 10)
    suf := make([][]int, 10)
    for i := range pre { pre[i] = make([]int, 10); suf[i] = make([]int, 10) }
    cnt1, cnt2 := make([]int, 10), make([]int, 10)
    for i := 0; i < n; i++ {
        d := int(s[i] - '0')
        for x := 0; x < 10; x++ { pre[x][d] += cnt1[x] }
        cnt1[d]++
    }
    for i := n-1; i >= 0; i-- {
        d := int(s[i] - '0')
        for x := 0; x < 10; x++ { suf[d][x] += cnt2[x] }
        cnt2[d]++
    }
    for i := 2; i < n-2; i++ {
        for a := 0; a < 10; a++ {
            for b := 0; b < 10; b++ {
                ans = (ans + pre[a][b]*suf[b][a]) % mod
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public int countPalindromes(String s) {
        int n = s.length(), mod = 1000000007, ans = 0;
        int[][] pre = new int[10][10], suf = new int[10][10];
        int[] cnt1 = new int[10], cnt2 = new int[10];
        for (int i = 0; i < n; i++) {
            int d = s.charAt(i) - '0';
            for (int x = 0; x < 10; x++) pre[x][d] += cnt1[x];
            cnt1[d]++;
        }
        for (int i = n-1; i >= 0; i--) {
            int d = s.charAt(i) - '0';
            for (int x = 0; x < 10; x++) suf[d][x] += cnt2[x];
            cnt2[d]++;
        }
        for (int i = 2; i < n-2; i++) {
            for (int a = 0; a < 10; a++) {
                for (int b = 0; b < 10; b++) {
                    ans = (int)((ans + 1L * pre[a][b] * suf[b][a]) % mod);
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun countPalindromes(s: String): Int {
        val n = s.length; val mod = 1_000_000_007; var ans = 0
        val pre = Array(10) { IntArray(10) }; val suf = Array(10) { IntArray(10) }
        val cnt1 = IntArray(10); val cnt2 = IntArray(10)
        for (i in 0 until n) {
            val d = s[i] - '0'
            for (x in 0..9) pre[x][d] += cnt1[x]
            cnt1[d]++
        }
        for (i in n-1 downTo 0) {
            val d = s[i] - '0'
            for (x in 0..9) suf[d][x] += cnt2[x]
            cnt2[d]++
        }
        for (i in 2 until n-2) {
            for (a in 0..9) for (b in 0..9) ans = ((ans + 1L * pre[a][b] * suf[b][a]) % mod).toInt()
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def countPalindromes(self, s: str) -> int:
        n, mod, ans = len(s), 10**9+7, 0
        pre = [[0]*10 for _ in range(10)]
        suf = [[0]*10 for _ in range(10)]
        cnt1 = [0]*10
        cnt2 = [0]*10
        for d in map(int, s):
            for x in range(10):
                pre[x][d] += cnt1[x]
            cnt1[d] += 1
        for d in map(int, reversed(s)):
            for x in range(10):
                suf[d][x] += cnt2[x]
            cnt2[d] += 1
        for a in range(10):
            for b in range(10):
                for i in range(2, n-2):
                    ans = (ans + pre[a][b] * suf[b][a]) % mod
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

impl Solution {
    pub fn count_palindromes(s: String) -> i32 {
        let n = s.len();
        let modn = 1_000_000_007;
        let s: Vec<u8> = s.bytes().collect();
        let mut pre = vec![vec![0; 10]; 10];
        let mut suf = vec![vec![0; 10]; 10];
        let mut cnt1 = vec![0; 10];
        let mut cnt2 = vec![0; 10];
        for &b in &s {
            let d = (b - b'0') as usize;
            for x in 0..10 { pre[x][d] += cnt1[x]; }
            cnt1[d] += 1;
        }
        for &b in s.iter().rev() {
            let d = (b - b'0') as usize;
            for x in 0..10 { suf[d][x] += cnt2[x]; }
            cnt2[d] += 1;
        }
        let mut ans = 0i64;
        for i in 2..n-2 {
            for a in 0..10 {
                for b in 0..10 {
                    ans = (ans + pre[a][b] as i64 * suf[b][a] as i64) % modn;
                }
            }
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    countPalindromes(s: string): number {
        const n = s.length, mod = 1e9+7;
        const pre = Array.from({length: 10}, () => Array(10).fill(0));
        const suf = Array.from({length: 10}, () => Array(10).fill(0));
        const cnt1 = Array(10).fill(0), cnt2 = Array(10).fill(0);
        for (let i = 0; i < n; i++) {
            const d = +s[i];
            for (let x = 0; x < 10; x++) pre[x][d] += cnt1[x];
            cnt1[d]++;
        }
        for (let i = n-1; i >= 0; i--) {
            const d = +s[i];
            for (let x = 0; x < 10; x++) suf[d][x] += cnt2[x];
            cnt2[d]++;
        }
        let ans = 0;
        for (let i = 2; i < n-2; i++) {
            for (let a = 0; a < 10; a++) {
                for (let b = 0; b < 10; b++) {
                    ans = (ans + pre[a][b] * suf[b][a]) % mod;
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) for prefix/suffix computation, O(n*100) for the final count, overall O(n) for practical n.
  • 🧺 Space complexity: O(1) for fixed-size arrays.