寻求线性时间复杂度的无聊连续子串计数算法方案

问题回顾 #

鲍勃每天需完成26种任务之一（用A-Z大写字母编码），部分天数可自选任务（标记为!）。需统计所有长度≥2的连续天数段（L<R）中，能让鲍勃每天执行同一任务的“无聊段”数量。无聊段满足以下任一条件：

• 段内所有字符为同一个非!字符；
• 段内包含至少一个!。

输入为长度N（1≤N≤1e6）的字符串，仅由大写字母和!组成；输出为无聊段总数。

你之前的嵌套循环实现时间复杂度为O(n²)，对于1e6规模的输入必然超时，下面给出O(n)的线性时间解法。

核心思路：反向计算 #

直接统计符合条件的无聊段比较繁琐，换个思路更高效：

1. 先算出所有长度≥2的连续段总数
2. 再减去不满足无聊段条件的段数（也就是：不含!且包含至少两种不同字母的段）
3. 最终结果就是无聊段的数量

步骤拆解 #

1. 计算总段数

长度为n的字符串，所有长度≥2的连续段总数公式为：

total = n * (n - 1) / 2

这是因为长度为2的段有n-1个，长度3的有n-2个，...，长度n的有1个，求和后就是等差数列的结果。

2. 计算非无聊段数

非无聊段只会出现在连续的纯字母块（即完全由非!字符组成的连续子串）中。对每个这样的块：

• 先算该块的总段数：block_total = len * (len - 1) / 2（len是块的长度）
• 再算该块中所有字符相同的连续子串的段数之和：比如块是"AAABBB"，其中"AAA"的相同段数是32/2=3，"BBB"是32/2=3，总和为6
• 该块的非无聊段数 = block_total - 相同字符段数之和
• 把所有纯字母块的非无聊段数相加，得到总的非无聊段数non_boring

3. 计算最终结果

无聊段总数 = 总段数 - 非无聊段数

Swift 实现代码 #

func solve() {
    guard let plan = readLine() else { return }
    let n = plan.count
    guard n >= 2 else {
        print(0)
        return
    }
    
    // 计算所有长度≥2的连续段总数
    let total = n * (n - 1) / 2
    var nonBoring = 0
    
    let chars = Array(plan)
    var i = 0
    
    while i < n {
        // 跳过所有含!的部分，定位到纯字母块的起始
        while i < n && chars[i] == "!" {
            i += 1
        }
        if i >= n {
            break
        }
        // 找到当前纯字母块的结束位置
        let start = i
        while i < n && chars[i] != "!" {
            i += 1
        }
        let blockLen = i - start
        if blockLen < 2 {
            continue // 长度不足2的纯字母块没有非无聊段
        }
        // 当前块的总段数
        let blockTotal = blockLen * (blockLen - 1) / 2
        // 计算块内相同字符连续子串的段数之和
        var sameSegmentSum = 0
        var currentChar = chars[start]
        var currentLen = 1
        for j in start+1..<i {
            if chars[j] == currentChar {
                currentLen += 1
            } else {
                sameSegmentSum += currentLen * (currentLen - 1) / 2
                currentChar = chars[j]
                currentLen = 1
            }
        }
        // 加上最后一段相同字符的段数
        sameSegmentSum += currentLen * (currentLen - 1) / 2
        // 累加当前块的非无聊段数
        nonBoring += blockTotal - sameSegmentSum
    }
    
    let result = total - nonBoring
    print(result)
}

复杂度分析 #

• 时间复杂度：O(n)，整个过程仅遍历字符串两次（一次分割纯字母块，一次处理每个块内的字符），每个字符仅被访问常数次，完全适配1e6规模的输入。
• 空间复杂度：O(n)，主要用于将字符串转为字符数组，在Swift中这个开销完全可控。

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