统计回文子序列数目

难度:

标签:

题目描述

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 10⁹ + 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 <= 10⁴
s consists of digits.

代码结果

运行时间: 152 ms, 内存: 16.7 MB

// 思路：
// 1. 使用字符流处理字符串，利用流的特性来进行回文子序列的查找。
// 2. 通过递归方式生成所有长度为5的子序列，并判断是否为回文。
// 3. 统计并返回回文子序列的个数。

import java.util.stream.IntStream;

public class PalindromicSubsequencesStream {
    private static final int MOD = 1000000007;

    public int countPalindromicSubsequences(String s) {
        return (int) IntStream.range(0, s.length())
            .mapToObj(i -> s.substring(i))
            .flatMap(str -> IntStream.range(1, str.length()).boxed()
                .map(j -> str.substring(0, j + 1)))
            .filter(sub -> sub.length() == 5 && isPalindrome(sub))
            .count() % MOD;
    }

    private boolean isPalindrome(String s) {
        int n = s.length();
        for (int i = 0; i < n / 2; i++) {
            if (s.charAt(i) != s.charAt(n - 1 - i)) return false;
        }
        return true;
    }
}

解释

方法:

本题解使用动态编程的方法来计算所有长度为5的回文子序列的数量。思路是使用多层哈希结构（数组）来维护字符的各种可能组合及其出现的次数和索引和。主要步骤分为：1) 更新a数组，它维护每个数字字符的出现次数；2) 更新b数组，它维护每种两字符组合的出现次数及索引和；3) 更新d数组，它维护每种四字符组合（形如ABCD）的出现次数；4) 通过对d数组的查询来统计所有可能的回文子序列。由于回文的特性，第五个字符必须与第一个字符相同，因此通过匹配这种模式来累计计数。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

在题解中，为何选择使用三层数组结构（a、b、d）来处理问题，而不是直接遍历所有长度为5的子序列来检查其是否为回文？

▷

直接遍历所有长度为5的子序列来检查是否为回文，虽然直观但效率较低，时间复杂度为O(n^5)，其中n是字符串的长度。使用三层数组结构（a、b、d）能够利用动态规划的方法，将问题分解为多个较小的子问题，并存储中间结果，从而避免重复计算，显著提升算法效率。数组a、b、d分别记录了不同长度组合的字符出现情况，使得通过更新和查询这些数组，可以在O(n)的时间复杂度内完成对所有长度为5的回文子序列的计数。

🦆

在计算五位回文子序列时，d数组是如何精确地利用之前记录的四字符组合和当前字符来更新回文子序列的计数的？

▷

d数组用于记录每种四字符组合的出现次数。在计算过程中，每遇到一个新字符，就尝试将其与之前记录的所有可能的三字符组合（由b数组记录）结合，形成新的四字符组合，同时更新d数组。当处理到字符串的某个位置时，对于当前字符，检查所有以此字符结尾能形成的四字符组合（即查看d数组），检查它们能否与之前的字符配对成为回文子序列。因此，d数组使得我们能够高效地统计所有可能的以当前字符结尾的回文子序列数量。

🦆

在更新d数组的步骤中，表达式`(i-1) * b[x][num][0] - b[x][num][1]`是如何工作的，它的目的是什么？

▷

这个表达式用于计算与当前字符配对的所有可能的三字符组合（由b数组记录）的更新。其中`b[x][num][0]`是到目前为止与当前字符配对的字符x的出现次数，而`b[x][num][1]`是这些字符出现位置的索引和。表达式中的`(i-1) * b[x][num][0] - b[x][num][1]`是计算所有以x和当前字符num为中心的三字符组合能形成的四字符组合的数量。这是通过计算当前位置i之前所有可能的配对位置与当前位置的差的和来实现的，从而确保更新d数组时能正确反映所有四字符组合的出现次数。

🦆

题解中提到，通过对d数组的查询来统计所有可能的回文子序列，那么能否详细解释如何通过d数组查询来得出最终的回文子序列数目？

▷

在每次处理字符串中的一个新字符时，我们通过查询d数组来统计可能的回文子序列。具体地，对于当前字符，如果它能与某个四字符组合形成回文（即当前字符等于该四字符组合的第一个字符），我们就通过查看d数组中记录的该四字符组合的出现次数来增加回文子序列的计数。这种方法确保了每次遇到一个可能的回文结尾时，能够快速查询并累加之前所有匹配的四字符组合的数量，从而高效地统计出所有长度为5的回文子序列的总数。

统计回文子序列数目

题目描述

代码结果

解释

代码细节讲解

相关问题