小U的好字符串

问题描述

小U定义了一个“好字符串”，它的要求是该字符串中不包含任意长度不小于2的回文子串。现在小U拿到了一个字符串，她想知道有多少个非空的子序列是“好字符串”。你的任务是帮助她计算出这些子序列的数量。

例如，对于字符串 "aba"，它的子序列中除了 "aa" 和 "aba" 以外，其余五个子序列都是“好字符串”。

注意：由于答案可能非常大，你需要对结果取 10^9+7进行输出。

测试样例

样例1：

输入：s = "aba"
输出：5

样例2：

输入：s = "aaa"
输出：3

样例3：

输入：s = "ghij"
输出：15

C++解题

理解问题

• 回文子串：一个字符串如果从左到右读和从右到左读是一样的，那么它就是回文子串。例如，"aba" 和 "aa" 都是回文子串。
• 好字符串：一个字符串如果不包含任何长度不小于2的回文子串，那么它就是好字符串。

数据结构的选择

• 我们可以使用动态规划（DP）来解决这个问题。动态规划可以帮助我们有效地计算出所有可能的子序列，并判断它们是否是好字符串

算法步骤

1. 定义状态：

   • 设 dp[i][j] 表示以字符 s[i] 结尾且长度为 j 的子序列是否是好字符串。
   • 初始状态：dp[i][1] = true 对于所有 i，因为单个字符总是好字符串。

2. 状态转移：

   • 对于每个字符 s[i]，我们需要检查所有可能的子序列长度 j（从2开始）。
   • 如果 s[i] 和 s[i-1] 相同，那么 dp[i][2] = false，因为 "aa" 是回文子串。
   • 对于长度大于2的子序列，我们需要检查 dp[i-1][j-1] 是否为 true，并且 s[i] 不与前面的字符形成回文子串。

3. 计算结果：

   • 最终结果是所有 dp[i][j] 为 true 的子序列的数量之和。

关键步骤解释

1. 初始化：

   • 我们使用一个二维数组 f，其中 f[i][j] 表示以字符 i 结尾且长度为 j 的子序列的数量。
   • 初始化所有元素为 0。

2. 状态转移：

   • 对于每个字符 ch，我们更新 f 数组。
   • 如果当前字符 x 与之前的字符 i 和 j 不同，则更新 f[j][x]。
   • 如果 f[j][x] 超过 MOD，则取模。

3. 计算结果：

   • 遍历 f 数组，统计所有子序列的数量，并对结果取模 10^9 + 7。

代码实现

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int MOD = 1e9 + 7;

int solution(const string& s) {
    int m = 26;
    vector<vector<int>> f(m + 1, vector<int>(m, 0));
    for (char ch : s) {
        int x = ch - 'a';
        for (int i = 0; i <= m; ++i) {
            if (i != x) {
                for (int j = 0; j < m; ++j) {
                    if (j != x) {
                        f[j][x] += f[i][j];
                        if (f[j][x] >= MOD) {
                            f[j][x] -= MOD;
                        }
                    }
                }
            }
        }
        f[m][x] += 1;
    }
    int ans = 0;
    for (int j = 0; j < m; ++j) {
        for (int i = 0; i <= m; ++i) {
            ans = (ans + f[i][j]) % MOD;
        }
    }
    return ans;
}

int main() {
    cout << (solution("aba") == 5) << endl;
    cout << (solution("aaa") == 3) << endl;
    cout << (solution("ghij") == 15) << endl;
    return 0;
}

Python解题

思路说明

题目要求计算一个字符串中所有不包含任意长度不小于2的回文子串的非空子序列的数量。核心在于如何判断一个子序列是否包含长度不小于2的回文子串。通过动态规划的方法，我们可以记录每个字符作为子序列结尾时，前一个字符的分布情况，从而避免生成回文子串。

解题过程

1. 初始化动态规划数组：

   • 使用一个二维数组 f，其中 f[i][j] 表示以字符 j 结尾且前一个字符为 i 的子序列数量。
   • f[m][x] 表示以字符 x 结尾且前一个字符为任意字符的子序列数量。

2. 遍历字符串：

   • 对于每个字符 ch，计算其对应的索引 x。
   • 更新动态规划数组 f，确保不生成回文子串。

3. 更新动态规划数组：

   • 对于每个字符 ch，遍历所有可能的前一个字符 i 和当前字符 j，更新 f[j][x]。
   • 如果 i 和 j 都不等于 x，则 f[j][x] 增加 f[i][j]。
   • 如果 f[j][x] 超过模数 mod，则取模。

4. 计算结果：

   • 最终结果为所有 f[i][j] 的和，取模后输出。

复杂度分析

• 时间复杂度：O(n×m^2)，其中 n 是字符串的长度，m 是字符集的大小（本题中为26）。
• 空间复杂度：O(m^2)，用于存储动态规划数组 f。

知识点扩展

• 动态规划：动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。本题中，我们通过动态规划数组 f 记录每个字符作为子序列结尾时，前一个字符的分布情况，从而避免生成回文子串。
• 字符串处理：字符串处理是计算机科学中的一个重要领域，涉及字符串的匹配、查找、替换等操作。本题中，我们通过遍历字符串，计算每个字符的索引，并更新动态规划数组。
• 模运算：模运算在处理大数问题时非常有用，可以避免数值溢出。本题中，我们通过模运算确保结果在合理范围内。

代码实现

def solution(s: str) -> int:
    m = 26
    f = [[0 for _ in range(m)] for _ in range(m + 1)]
    mod = 10 ** 9 + 7
    for ch in s:
        x = ord(ch) - ord('a')
        for i in range(m + 1):
            if i != x:
                for j in range(m):
                    if j != x:
                        f[j][x] += f[i][j]
                        if f[j][x] >= mod:
                            f[j][x] -= mod
        f[m][x] += 1
    ans = (sum(f[i][j] for j in range(m) for i in range(m + 1))) % mod
    return ans


if __name__ == '__main__':
    print(solution(s = "aba") == 5)
    print(solution(s = "aaa") == 3)
    print(solution(s = "ghij") == 15)