235小U的好字符串

题目描述

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

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

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

题解

解题思路

题目中要求求出一个字符串中不包含任意长度不小于 2 的回文子串的子序列的数量。这里我们可以使用动态规划的方法来解决这个问题。任意一个长度大于等于 3 的回文串，一定包含一个长度为 2 的回文串或者长度为 3 的字符串。所以我们可以记录子序列中选择的前两个字符，然后遍历字符串，如果当前字符和前两个字符都不相等，那么我们可以选择当前字符，否则我们只能选择不选择当前字符。最后我们将所有的选择情况相加即可。

代码实现

# 记忆化搜索
# from functools import cache
# def solution(s: str) -> int:
#     mod = int(1e9 + 7)
#     def dfs(i, pre1, pre2):
#         if i == len(s):
#             return 1
#         res = 0
          # 不选择当前字符
#         res += dfs(i + 1, pre1, pre2)
#         if s[i] != pre1 and s[i] != pre2:
#             res += dfs(i + 1, pre2, s[i])
#         return res
      # 不包含空序列
#     res = dfs(0, -1, -1) - 1
#     return res

# 动态规划
mod = int(1e9 + 7)
def solution(s: str) -> int:
    n = len(s)
    m = 26
    f = [[0] * (m + 1) for _ in range(m + 1)]
    for ch in s:
        c = ord(ch) - ord('a')
        for i in range(27):
            if i == c:
                continue
            for j in range(27):
                if j == c:
                    continue
                f[j][c] += f[i][j]
                f[j][c] %= mod
        f[-1][c] += 1
    res = sum(sum(f[i]) for i in range(27))
    return res


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

复杂度分析

• 时间复杂度：$O(nm^2)$
• 空间复杂度：$O(m^2)$