Count different palindromic subsequences

/*
 * Given a string s, return the number of different non-empty palindromic subsequences in s. Since the answer may be very large, return it modulo 109 + 7.
 * A subsequence of a string is obtained by deleting zero or more characters from the string.
 * A sequence is palindromic if it is equal to the sequence reversed.
 * Two sequences a1, a2, ... and b1, b2, ... are different if there is some i for which ai != bi.
 * Example 1:
 * Input: s = "bccb"
 * Output: 6
 * Explanation: The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'.
 * Note that 'bcb' is counted only once, even though it occurs twice.
 * Example 2:
 * Input: s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba"
 * Output: 104860361
 * Explanation: There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 109 + 7.
 * Constraints:
 * 1 <= s.length <= 1000
 * s[i] is either 'a', 'b', 'c', or 'd'.
 */
// 730. Count Different Palindromic Subsequences
// Count distinct non-empty palindromic subsequences in s (only 'a','b','c','d').
// Return answer mod 10^9+7.

impl Solution {
  pub fn count_palindromic_subsequences(s: String) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = s.len();
    let s: Vec<usize> = s.bytes().map(|b| (b - b'a') as usize).collect();
    // dp[i][j] = # distinct palindromic subsequences in s[i..=j]
    let mut dp = vec![vec![0i64; n]; n];
    for i in 0..n {
      dp[i][i] = 1;
    }
    for len in 2..=n {
      for i in 0..=n - len {
        let j = i + len - 1;
        for c in 0..4usize {
          let l = (i..=j).find(|&k| s[k] == c);
          let r = (i..=j).rev().find(|&k| s[k] == c);
          match (l, r) {
            (None, _) | (_, None) => {}
            (Some(l), Some(r)) if l == r => dp[i][j] += 1,
            (Some(l), Some(r)) if l + 1 == r => dp[i][j] += 2,
            (Some(l), Some(r)) => {
              dp[i][j] = (dp[i][j] + dp[l + 1][r - 1] + 2) % MOD;
            }
          }
        }
        dp[i][j] %= MOD;
      }
    }
    dp[0][n - 1] as i32
  }
}