传智杯 第六届—E

题目描述：

        leafee 最近爱上了 abb 型语句，比如“叠词词”、“恶心心”。 leafee 拿到了一个只含有小写字母的字符串，她想知道有多少个 "abb" 型的子序列？

定义： abb 型字符串满足以下条件：

1. 字符串长度为 3 。

2. 字符串后两位相同。

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;
}