?題目鏈接：

DP36 abb

?題目描述?

leafee 最近愛上了 abb 型語句，比如“疊詞詞”、“惡心心”

leafee 拿到了一個只含有小寫字母的字符串，她想知道有多少個 "abb" 型的子序列？
定義： abb 型字符串滿足以下條件：

1. 字符串長度為 3 。
2. 字符串后兩位相同。
3. 字符串前兩位不同。

?輸入描述:

第一行一個正整數?𝑛n

第二行一個長度為?𝑛n?的字符串（只包含小寫字母）

1≤𝑛≤1051≤n≤105

?輸出描述:

"abb" 型的子序列個數。?

?示例1

📍輸入

6 abcbcc

📍輸出

8

📍說明

共有1個abb，3個acc，4個bcc?

?解題思路

?動態規劃：

1. 初始化計數器和數組：

   • f[26]：用來記錄每個字母對結果的當前貢獻。
   • g[26]：用來記錄每個字母的出現次數。
   • res：結果變量，用來存儲符合條件的子序列個數。
   • i：用來記錄當前遍歷到的字符的索引。

2. 遍歷字符串：

   • 對于字符串中的每一個字符e：
     1. 將當前字符對結果的貢獻加到res中。
     2. 更新字符e的貢獻值：f[e-'a'] = f[e-'a'] + i - g[e-'a']。
        • i代表當前字符之前的所有字符數。
        • g[e-'a']是當前字符e之前出現的所有字符e的次數。
        • 通過計算i - g[e-'a']，得到當前字符e之前所有非e字符的數量。
     3. 更新字符e的出現次數：g[e-'a'] += 1。
     4. 增加遍歷索引i。

?貢獻值可以理解為在這以前區間有多少個? ? _ x? ?（假設現在 i 位置字符為x）?

?代碼
?

#include <iostream>
using namespace std;int main() {int n;cin >> n;string str;cin >> str;long long res = 0;int f[26]={0};int g[26]={0};long long i=0;for(auto e:str){res+=f[e-'a'];f[e-'a']=f[e-'a']+i-g[e-'a'];g[e-'a']=g[e-'a']+1;i++;}cout << res << endl;return 0;
}

---

※ 如果文章對你有幫助的話，可以點贊收藏！！謝謝支持