本文共 1023 字，大约阅读时间需要 3 分钟。

为了解决这个问题，我们需要计算给定字符串中能形成多少个" PAT "。这里的" PAT "并非连续的三个字符，而是三个字符分别在三个不同的位置上。

方法思路

为了高效地解决这个问题，我们可以采用以下方法：

这种方法的时间复杂度是O(n)，适合处理长度为10^5的字符串。

解决代码

s = input().strip()n = len(s)MOD = 10**9 + 7# 预处理count_T数组：count_T[i]表示从i后面（包括i+1）到末尾的T的数量count_T = [0] * (n + 1)for i in range(n-1, -1, -1):    if s[i] == 'T':        count_T[i] = count_T[i+1] + 1    else:        count_T[i] = count_T[i+1]# 预处理count_P数组：count_P[i]表示前面（包括0到i-1）有多少个Pcount_P = [0] * (n + 1)for i in range(n):    count_P[i+1] = count_P[i] + (1 if s[i] == 'P' else 0)# 计算结果res = 0for j in range(n):    if s[j] == 'A':        res = (res + count_P[j] * count_T[j+1]) % MODprint(res % MOD)

代码解释

这种方法确保了我们在O(n)时间复杂度内解决问题，适用于大规模输入。

转载地址：http://mxvfk.baihongyu.com/