返回题库

回文子序列计数

Count Palindromic Subsequences

专题
Algorithmic Programming / 算法编程
难度
L4
来源
Citadel

题目详情

问题：回文子序列计数

考察：字符串、动态规划

来源：Citadel

链接：https://www.jointaro.com/interviews/questions/count-palindromic-subsequences/

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.
解析

思路：区间 DP。令 dp[l][r] 表示子串 s[l..r] 的不同回文子序列数量，根据两端字符是否相等分情况转移；相等时还要寻找内部相同字符位置来避免重复计数。

复杂度：时间 O(n^2) 到 O(n^3)，取决于内部相同字符查找是否预处理；空间 O(n^2)。