求O(n)时间复杂度下统计含子序列‘tira’的子串数量解法

要解决统计字符串中包含子序列“tira”的子串数量问题，我们可以通过计算总子串数减去不包含该子序列的子串数的方式，实现O(n)时间复杂度的解决方案，避免原O(n³)实现的低效问题。

思路分析 #

总子串数公式为 n*(n+1)//2（n为字符串长度）。我们只需要统计所有不包含“tira”子序列的子串数量，用总子串数减去这个值即可得到答案。

不包含“tira”子序列的子串分为四类：

1. 完全不包含字符't'的子串
2. 包含't'但不存在't'在'i'之前的子串（即没有子序列“ti”）
3. 包含“ti”但不存在'ti'在'r'之前的子串（即没有子序列“tir”）
4. 包含“tir”但不存在'tir'在'a'之前的子串（即没有子序列“tira”）

我们用动态规划维护四个变量，跟踪以当前字符结尾的各类子串数量，逐步累积统计总数：

• curr_no_t：以当前字符结尾，不包含't'的子串数
• curr_has_t_no_ti：以当前字符结尾，包含't'但不包含“ti”的子串数
• curr_has_ti_no_tir：以当前字符结尾，包含“ti”但不包含“tir”的子串数
• curr_has_tir_no_tira：以当前字符结尾，包含“tir”但不包含“tira”的子串数

通过遍历每个字符，根据字符类型更新这四个变量，并累积到总统计变量中。

实现代码 #

def count_tira_substrings(s):
    n = len(s)
    total_substrings = n * (n + 1) // 2

    # 初始化以当前字符结尾的各类子串数量
    prev_no_t = 0
    prev_has_t_no_ti = 0
    prev_has_ti_no_tir = 0
    prev_has_tir_no_tira = 0

    # 初始化各类子串的总数量
    total_no_t = 0
    total_has_t_no_ti = 0
    total_has_ti_no_tir = 0
    total_has_tir_no_tira = 0

    for c in s:
        # 计算当前字符对应的各类子串数量
        curr_no_t = 0
        curr_has_t_no_ti = 0
        curr_has_ti_no_tir = 0
        curr_has_tir_no_tira = 0

        if c != 't':
            curr_no_t = prev_no_t + 1
        else:
            curr_has_t_no_ti = prev_no_t + 1 + prev_has_t_no_ti

        if c not in ('t', 'i'):
            curr_has_t_no_ti = prev_has_t_no_ti
        elif c == 'i':
            curr_has_ti_no_tir = prev_has_t_no_ti + prev_has_ti_no_tir

        if c not in ('i', 'r'):
            curr_has_ti_no_tir = prev_has_ti_no_tir
        elif c == 'r':
            curr_has_tir_no_tira = prev_has_ti_no_tir + prev_has_tir_no_tira

        if c not in ('r', 'a'):
            curr_has_tir_no_tira = prev_has_tir_no_tira

        # 更新总统计数
        total_no_t += curr_no_t
        total_has_t_no_ti += curr_has_t_no_ti
        total_has_ti_no_tir += curr_has_ti_no_tir
        total_has_tir_no_tira += curr_has_tir_no_tira

        # 更新前序状态为当前状态
        prev_no_t, prev_has_t_no_ti, prev_has_ti_no_tir, prev_has_tir_no_tira = \
            curr_no_t, curr_has_t_no_ti, curr_has_ti_no_tir, curr_has_tir_no_tira

    # 总符合条件的子串数 = 总子串数 - 不包含tira的子串数
    non_tira = total_no_t + total_has_t_no_ti + total_has_ti_no_tir + total_has_tir_no_tira
    return total_substrings - non_tira

# 测试示例
if __name__ == '__main__':
    print(count_tira_substrings("aritaritaritaritarit")) # 48
    print(count_tira_substrings("rtiraaar")) # 8
    print(count_tira_substrings("ritari")) # 0
    print(count_tira_substrings("taikurinhattu")) # 4
    print(count_tira_substrings("ttiirraa")) # 4
    print(count_tira_substrings("tixratiyra")) # 11
    print(count_tira_substrings("aotiatraorirratap")) # 42

代码验证 #

上述代码运行后，所有测试示例的输出均与原O(n³)实现一致，但时间复杂度优化为O(n)，仅需遍历字符串一次，空间复杂度为O(1)，适合处理长字符串场景。

内容的提问来源于stack exchange，提问作者jdbbgkjnd