传智杯 第六届—E
题目描述：
leafee 最近爱上了 abb 型语句，比如“叠词词”、“恶心心”。 leafee 拿到了一个只含有小写字母的字符串，她想知道有多少个 "abb" 型的子序列？
定义： abb 型字符串满足以下条件：
-
字符串长度为 3 。
-
字符串后两位相同。
-
字符串前两位不同。
输入描述:
第一行一个正整数 n
第二行一个长度为 n 的字符串（只包含小写字母）(1≤n≤10^5)
输出描述:
"abb" 型的子序列个数。
示例1
输入:
6
abcbcc输出:
8说明:
共有1个abb，3个acc，4个bcc
示例2
输入:
4
abbb输出:
3解题思路：
本题是求字符串中所以的abb序列，我们采用的方法是先将字符串中的所有字符的个数记录下来，分别存储在char_number数组的对应位置，例如字符a的个数存储在char_number[0]的位置。然后依次遍历整个字符串，找到该字符后面所有字符的个数（char_number），当某个字符与该字符不同且其个数>2，那么就会产生以该字符为首的abb序列，其个数为，然后再将该字符所对应的char_number数-1，代表后面该字符的个数-1，最终循环结束过后，就可以得到所以的序列个数。
注意：
①当字符串长度过大时，可能会导致最终计算得到的序列个数较大，所以不能采用int型来记录序列个数，可以采用long long型来记录序列个数；
②本题的问题是求得字符串中所有的序列，而不是连续的序列abb；
③采用3个循环得到的运行会超时，所以最多只能采用两个循环。
代码：
#include<iostream>
using namespace std;
int main()
{//创建一维动态数组int num; //用于存储字符的个数cin>>num;char *ch = new char[num];//输入字符for(int i=0;i<num;i++){cin>>ch[i];}//查找long long total = 0; //用于记录abb型序列的个数int char_number[27] = {0};//记录每个字符的个数for(int i=0;i<num;i++){//将每个字符对应的数组下标i所对应的值+1,例如a对应数组下标0，若ch[j]='a',则char_number[0]++char_number[ch[i]-97]++;} //若j后面含有n个相同的字符，则会构成n-1个abb序列（其中n>1）for(int j=0;j<num-2;j++){for(int k=0;k<26;k++){if(char_number[k] > 1 && k != int(ch[j]-97)){total += char_number[k] * (char_number[k]-1) / 2;}}//将这个字符在数组中的个数-1（用于记录在这个字符后面的各个字符个数）char_number[int(ch[j]-97)]--;}cout<<total<<endl;system("pause");return 0;
}