当前位置：首页 > article >正文

【算法】 ‘abb‘ 型子序列问题——前后缀分解 python

article 2025/2/26 13:48:21

‘abb’ 型子序列

题目描述

leafee 最近爱上了 abb 型语句，比如“叠词词”、“恶心心”
leafee 拿到了一个只含有小写字母的字符串，她想知道有多少个 “abb” 型的子序列？
定义： abb 型字符串满足以下条件：
字符串长度为 3 。字符串后两位相同。字符串前两位不同。

输入描述:

第一行一个正整数 𝑛
第二行一个长度为 𝑛的字符串（只包含小写字母） 1≤𝑛≤1e5

输出描述:

“abb” 型的子序列个数。

示例1

输入

6
abcbcc

输出

说明
共有1个abb，3个acc，4个bcc

示例2

输入

4
abbb

输出

第一种做法：枚举第一个 `a`，在后缀中寻找 `bb`

思路：

目标：统计满足条件的三元组 (a, b, b)，其中 a 是第一个字符，b 是后两个字符，且 a != b。
后缀和数组：
- 使用后缀和数组 suf[i][c] 表示从位置 i 开始到字符串末尾，字符 c 的出现次数。
- 通过从后向前遍历字符串，填充后缀和数组。
枚举第一个字符 a：
- 对于每个位置 i，假设 s[i] 是 a。
- 在后缀中（即从 i+1 开始）寻找字符 b，且 b 至少出现两次。
- 如果找到满足条件的 b，则累加组合数 C(k, 2)，其中 k 是字符 b 在后缀中的出现次数。
组合数计算：
- 对于字符 b 在后缀中出现 k 次，符合条件的 bb 组合数为 k * (k - 1) // 2。

AC_code：

n = int(input())
s = [ord(x) - ord('a') for x in input()]
ans = 0
# 后缀和数组，suf[i][c] 表示从位置i到末尾字符c的出现次数
suf = [[0] * 26 for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
    for c in range(26):
        suf[i][c] = suf[i + 1][c]
    suf[i][s[i]] += 1

for i in range(n):
    for j in range(26):
        if j != s[i] and suf[i + 1][j] >= 2:
            ans += suf[i + 1][j] * (suf[i + 1][j] - 1) // 2
print(ans)

时间复杂度：

后缀和数组的构建：O(n * 26)。
枚举第一个字符并计算组合数：O(n * 26)。
总时间复杂度：O(n * 26)。

第二种做法：枚举中间 `b`，分别在前缀中找 `a`，后缀中找 `b`

思路：

目标：统计满足条件的三元组 (a, b, b)，其中 b 是中间字符，a 是左边字符，且 a != b。
前缀和数组：
- 使用前缀和数组 pre[i][c] 表示前 i 个字符中字符 c 的出现次数。
- 通过从前向后遍历字符串，填充前缀和数组。
后缀和数组：
- 使用后缀和数组 suf[i][c] 表示从位置 i 开始到末尾，字符 c 的出现次数。
- 通过从后向前遍历字符串，填充后缀和数组。
枚举中间字符 b：
- 对于每个位置 j，假设 s[j] 是 b。
- 在左边（即前 j 个字符）寻找字符 a，且 a != b。
- 在右边（即从 j+1 开始）寻找字符 b。
- 符合条件的组合数为左边 a 的数量乘以右边 b 的数量。
累加结果：
- 对于每个中间字符 b，累加 left * right 到答案中。

AC_code：

n = int(input())
s = [ord(x) - ord('a') for x in input()]

# 前缀和数组:pre[i][c]表示前i个字符中字符c的出现次数
pre = [[0] * 26 for _ in range(n + 1)]
for i in range(n):
    for c in range(26):
        pre[i + 1][c] = pre[i][c]
    pre[i + 1][s[i]] += 1

# 后缀和数组:suf[i][c]表示从位置i到末尾字符c的出现次数
suf = [[0] * 26 for _ in range(n + 2)]
for i in range(n - 1, -1, -1):
    for c in range(26):
        suf[i][c] = suf[i + 1][c]
    suf[i][s[i]] += 1

ans = 0
for i in range(n):
    # 左边不等于s[i]的字符数
    left = sum(pre[i][c] for c in range(26) if c != s[i])
    # 右边等于s[i]的字符数
    right = suf[i + 1][s[i]]
    ans += left * right
print(ans)

时间复杂度：

前缀和数组的构建：O(n * 26)。
后缀和数组的构建：O(n * 26)。
枚举中间字符并计算结果：O(n * 26)。
总时间复杂度：O(n * 26)。

比较：

思路差异：
- 第一种做法是枚举第一个字符 a，然后在后缀中寻找 bb。
- 第二种做法是枚举中间字符 b，然后分别在前缀中找 a，后缀中找 b。
实现复杂度：
- 两种方法都需要构建前缀和和后缀和数组，实现复杂度相似。
适用场景：
- 第一种方法更适合直接统计 (a, b, b) 的组合。
- 第二种方法更适合统计中间字符固定的组合。
性能：
- 两种方法的时间复杂度相同，均为 O(n * 26)，性能相近。