算法优化需求：O(n)时间求解可构造'tira'的子串总数

问题分析 #

我们需要统计所有连续子串，使得该子串可通过删除多余字符构造出"tira"（即子串中存在顺序为t→i→r→a的字符）。现有代码通过字符串操作和嵌套循环生成子串对，时间复杂度极高（最坏情况O(n²)甚至更高），无法处理10⁵长度的输入。

核心思路 #

换正向计算方式：对每个起始位置L，找到最小的结束位置R_min，使得子串s[L..R_min]已包含顺序的t→i→r→a。所有R ≥ R_min的子串s[L..R]都符合要求，贡献数量为n - R_min（n为字符串长度）。

为快速定位每个位置之后的下一个目标字符，通过反向遍历预处理四个数组：

• next_t[i]：从位置i开始（含i），下一个t的位置，不存在则为n
• next_i[i]：从位置i开始，下一个i的位置，不存在则为n
• next_r[i]：从位置i开始，下一个r的位置，不存在则为n
• next_a[i]：从位置i开始，下一个a的位置，不存在则为n

预处理完成后，遍历每个起始位置L，依次找到t→i→r→a的位置链，若链完整则累加对应子串数量。

优化代码实现 #

def count_tira_substrings(s):
    n = len(s)
    if n < 4:
        return 0
    
    # 预处理四个next数组，反向遍历
    next_t = [n] * n
    last_t = n
    for i in range(n-1, -1, -1):
        if s[i] == 't':
            last_t = i
        next_t[i] = last_t
    
    next_i = [n] * n
    last_i = n
    for i in range(n-1, -1, -1):
        if s[i] == 'i':
            last_i = i
        next_i[i] = last_i
    
    next_r = [n] * n
    last_r = n
    for i in range(n-1, -1, -1):
        if s[i] == 'r':
            last_r = i
        next_r[i] = last_r
    
    next_a = [n] * n
    last_a = n
    for i in range(n-1, -1, -1):
        if s[i] == 'a':
            last_a = i
        next_a[i] = last_a
    
    total = 0
    for L in range(n):
        # 找到L之后的第一个t
        t_pos = next_t[L]
        if t_pos == n:
            continue
        # 找到t之后的第一个i
        i_pos = next_i[t_pos + 1]
        if i_pos == n:
            continue
        # 找到i之后的第一个r
        r_pos = next_r[i_pos + 1]
        if r_pos == n:
            continue
        # 找到r之后的第一个a
        a_pos = next_a[r_pos + 1]
        if a_pos == n:
            continue
        # 所有R >= a_pos的子串都符合条件
        total += (n - a_pos)
    
    return total

if __name__ == "__main__":
    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(n)
• 整体时间复杂度O(n)，空间复杂度O(n)，完全支持10⁵长度的输入。

验证示例 #

以输入"tixratiyra"为例，预处理后遍历每个起始位置，计算得到的总贡献为11，与示例结果一致。

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