我正在尝试解决以下算法问题：
每天，鲍勃都会去上班，并完成 26 项可能的任务之一。这些任务用英文字母从 a 到 z 编码。有时鲍勃会执行老板分配的任务，有时他可以选择自己完成这 26 项可能的任务中的哪一项。这样的日子用符号 标记
!。老板已经为鲍勃制定了未来 N 天的工作计划。鲍勃非常不喜欢连续几天做同样的任务，为了向老板表明他有多无聊，他决定计算有多少种方法可以选择一个至少两天的连续时间段，在此期间他每天都执行相同的任务。也就是说，Bob 考虑从 L 天到 R 天的所有可能的时间段，其中 L < R，并且如果他选择自己的工作时，该时间段内所有日子的任务都是相同的，那么他认为该时间段很无聊。
趁Bob无聊的时候，帮他确定接下来N天的工作计划中无聊的段数。
输入格式
输入一行，由大写英文字母和符号!组成的字符序列——未来N（1≤N≤1000000）天的工作计划。
输出格式
输出一个数字——计划中的钻孔段数。
示例 1
输入：
a!b!c输出：5
示例 2
输入：
a!输出：1
笔记
第一个例子中所有可能的段都在
|和之间||a!|b!c a|!b|!c a|!b!|c a!|b!|c a!b|!c|
我将任务正式化如下：
问题
给定一个 N 天的工作计划，以大写英文字母（'a' 到 'z'）和感叹号（'!'）组成的字符串形式，计算至少两天的连续片段的数量（即从 L 天到 R 天，其中 1≤L<R≤N），使得 Bob 可以在该片段内的每一天执行相同的任务。如果满足以下任一条件，则认为该片段“无聊”：
该段内的所有字符都是相同的非“！”字符。
该片段至少包含一个感叹号（“！”）。
输入
表示 N 天工作计划的单个字符串。
该字符串仅包含大写英文字母（“a”到“z”）和感叹号（“！”）。
字符串 N 的长度介于 1 到 1,000,000 之间（包括 1 和 1,000,000）（1≤N≤10 6）。
输出
一个整数，表示给定工作计划中“无聊”段的总数。
我的代码
func solve() {
guard let plan = readLine() else { return }
let n = plan.count
let planArray = Array(plan)
var boringSegmentCount = 0
for i in 0..<n {
var nonWildcards = Set<Character>()
for j in i..<n {
if planArray[j] != "!" {
nonWildcards.insert(planArray[j])
}
if j > i && nonWildcards.count <= 1 {
boringSegmentCount += 1
}
}
}
print(boringSegmentCount)
}
提供的 Swift 代码旨在通过遍历输入字符串的所有可能的连续段来解决问题plan。
它使用嵌套循环来遍历字符串所有可能的连续段：
- 外层循环（
i）确定段的起始索引。 - 内层循环（
j）确定段的结束索引。
对于每个段（从索引i到j）：
- 它创建了一个
Set用来nonWildcards存储非“！”的唯一字符的调用。 - 它遍历当前段内的字符。
- 如果字符不是“！”，则会将其添加到
nonWildcards集合中。 - 它检查段的长度是否大于 1 (
j > i) 以及段中唯一非通配符的数量是否最多为 1 (nonWildcards.count <= 1)。 - 如果两个条件都为真，则它会增加
boringSegmentCount。
该算法的主要问题是其二次时间复杂度 O(n²)，因此对于较大的值n（如问题中所述，最高为 1,000,000），该算法可能非常慢并导致超出时间限制的错误。
我的问题
有没有可能针对这个任务提出一个渐近性更低的算法？我想这个问题可以在线性时间内解决，但遗憾的是，我仍然想不出合适的逻辑。