1.思路（算法：1维的类DP...）

核心逻辑：逆向统计三元组贡献

----题目要求统计满足 $i<j<k$ 且 $S_i=S_k$ 的三元组数量，等价于对每个字符作为三元组的第三个元素（位置 k ），统计之前能与之配对的第一个元素（位置 i ）的数量，再乘以中间可插入的第二个元素（位置 j ）的数量。

算法步骤

• 状态定义：
  c[j]：记录当前字符之前，第j个字母的出现次数
  a[j]：记录当前字符之前，以第j个字母为开头的合法三元组数量（即所有满足 $i<j<当前位置$ 且 $S_i=第j个字母$ 的三元组数量）

• 动态更新：
  遍历字符串时，将当前字符作为三元组的第三个元素，累加之前能形成的合法三元组数量到 ans
  更新所有字母的三元组计数：每个字母的三元组数量 += 该字母的出现次数
  增加当前字母的出现次数

• 时间复杂度：$O(|S|)$

---

2.参考代码

#include <iostream>
#include <string>
using namespace std;
int main(){
    string s;
    cin>>s;
    long long a[26]={0};//1.1记录当前字符前以第j个字母开头的合法三元组数量
    long long c[26]={0};//1.2记录当前字符前第j个字母的出现次数
    long long ans=0;//1.3累计所有合法三元组数量
/***********************************核心代码*****************************************/
    for(int i=0;i<s.size();i++){
        ans+=a[s[i]-'A'];//2.1将当前字符作为三元组第三个字符，累加合法数量
        for(int j=0;j<26;j++){
            a[j]+=c[j];//2.2更新每个字母的三元组计数
        }
        c[s[i]-'A']++;//2.3当前字母出现次数+1
    }
/************************************************************************************/
    cout<<ans<<"\n";
    return 0;
}