Python算法题: 计算字符串中满足特定规则的合法子串数量

本文将介绍如何使用Python实现一个算法，用于计算给定字符串中满足特定规则的合法子串数量。

问题描述：

给定一个只包含小写字母的字符串 s，如果一个字符串中不包含连续的三个相同字母，并且不存在两个相同的字母紧挨着两个相同的字母，那么这个字符串就是合法的。例如，字符串 'aaa' 是不合法的，字符串 'aabb' 也是不合法的。字符串 'aab' 是合法的。请问给出的字符串中有多少个合法子串。例如，输入为 'aabbaa'，输出为 16，原因是长度为 1, 2, 3, 4 的合法子串数量分别为 6, 5, 4, 1。

Python代码实现：


    # 统计长度为 1 的合法子串数量    count += n

    # 统计长度为 2 的合法子串数量    for i in range(n - 1):        if s[i] != s[i + 1]:            count += 1

    # 统计长度为 3 及以上的合法子串数量    for i in range(2, n):        if s[i] != s[i - 1] or s[i] != s[i - 2] or s[i - 1] != s[i - 2]:            count += (n - i)

    return count

s = 'aabbaa'result = countValidSubstrings(s)print(result)

**代码解析：**

1. **初始化：** 首先，我们获取字符串 `s` 的长度 `n`，并初始化一个计数器 `count` 为 0，用于存储合法子串的数量。
2. **统计长度为 1 的子串：** 由于单个字符必然合法，所以长度为 1 的合法子串数量等于字符串的长度 `n`，我们直接将 `count` 加上 `n`。
3. **统计长度为 2 的子串：** 我们遍历字符串，比较相邻的两个字符。如果它们不相等，则说明这是一个合法的长度为 2 的子串，将 `count` 加 1。
4. **统计长度大于等于 3 的子串：** 从字符串的第三个字符开始遍历，每次判断当前字符与其前两个字符是否满足合法条件。如果满足，则意味着以当前字符结尾的所有长度大于等于 3 的子串都是合法的。由于以 `s[i]` 结尾的子串数量为 `n - i`，我们将 `count` 加上 `n - i`。
5. **返回结果：** 最后，我们返回 `count`，即为字符串 `s` 中合法子串的总数。

**时间复杂度：**

该算法的时间复杂度为 O(n)，其中 n 是字符串的长度，因为它只对字符串进行了一次遍历。

希望本文能够帮助您理解如何使用 Python 实现计算字符串中满足特定规则的合法子串数量的算法。该算法思路清晰，代码简洁易懂，具有一定的参考价值。如果您有任何问题或建议，请随时提出。