字符串 APPAPT 中包含了两个单词 PAT，其中第一个 PAT 是第 2 位(P)，第 4 位(A)，第 6 位(T)；第二个 PAT 是第 3 位(P)，第 4 位(A)，第 6 位(T)。
现给定字符串，问一共可以形成多少个 PAT？
输入格式：
输入只有一行，包含一个字符串，长度不超过105，只包含 P、A、T 三种字母。
输出格式：
在一行中输出给定字符串中包含多少个 PAT。由于结果可能比较大，只输出对 1000000007 取余数的结果。
输入样例：
APPAPT
输出样例：
2
思路
- 显然暴力搜索是会超时的，毕竟数量级是(10^5)
- 目标字符串
PAT才三个字符，可以转化为：数P的个数，数T的个数，考察每个A的位置，将P和T的个数相乘就能得到结果，基本的排列组合的思想
代码
#include<bits/stdc++.h>
using namespace std; //设当前位置为i，字符段长度为len
int lp[100010] = {0}; //区间[0,i]的P的个数
int rt[100010] = {0}; //区间[i,len-1]的T的个数
const int MOD = 1000000007;
int main()
{
string pat;
getline(cin, pat);
for(int i=0;i<pat.size();i++)
if(pat[i] == 'P')
lp[i] = lp[i-1] + 1;
else
lp[i] = lp[i-1]; //数P
for(int i=pat.size()-1;i>=0;i--)
if(pat[i] == 'T')
rt[i] = rt[i+1] + 1;
else
rt[i] = rt[i+1]; //数T
int ans = 0;
for(int i=0;i<pat.size();i++)
if(pat[i] == 'A')
ans = (ans + lp[i] * rt[i]) % MOD; //在每个A的位置让两边的可能相乘就得到了经过当前位置A会有多少个PAT，累加起来就是答案
cout << ans;
return 0;
}
引用
https://pintia.cn/problem-sets/994805260223102976/problems/994805282389999616