Count palindromic subsequences

String Dynamic Programming

41.0% acceptance

Feb 25, 2026

609

Given a string of digits s, return the number of palindromic subsequences of s having length 5, modulo 10^9 + 7.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_palindromes(s: String) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let s: Vec<u8> = s.bytes().map(|b| b - b'0').collect();
    let n = s.len();
    let mut ans = 0i64;

    // A length-5 palindrome: d1 d2 X d2 d1
    for d1 in 0..10u8 {
      for d2 in 0..10u8 {
        // suffix[m] = # of "d2 d1" subsequences in s[m+1..]
        let mut suffix = vec![0i64; n];
        let mut cnt_right = 0i64;
        let mut suf = 0i64;
        for m in (0..n).rev() {
          suffix[m] = suf;
          if s[m] == d2 { suf = (suf + cnt_right) % MOD; }
          if s[m] == d1 { cnt_right += 1; }
        }

        // Prefix scan: pref = # of "d1 d2" subsequences in s[0..m-1]
        let mut pref = 0i64;
        let mut cnt_left = 0i64;
        for m in 0..n {
          ans = (ans + pref * suffix[m]) % MOD;
          if s[m] == d2 { pref = (pref + cnt_left) % MOD; }
          if s[m] == d1 { cnt_left += 1; }
        }
      }
    }
    ans as i32
  }
}