1.简述:
leafee 最近爱上了 abb 型语句,比如“叠词词”、“恶心心”
leafee 拿到了一个只含有小写字母的字符串,她想知道有多少个 "abb" 型的子序列?定义: abb 型字符串满足以下条件:
字符串长度为 3 。
字符串后两位相同。
字符串前两位不同。
第一行一个正整数
第二行一个长度为 的字符串(只包含小写字母)
"abb" 型的子序列个数。
输入:
6
abcbcc
输出:
8
说明:
共有1个abb,3个acc,4个bcc
输入:
4
abbb
输出:
3
2.代码实现:
import java.util.*;标签:yyds,abb,suffix,int,res,干货,str,字符串 From: https://blog.51cto.com/u_15488507/5848569
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
//输入字符串
String str=sc.next();
//后缀和数组,suffix[i+1][j]表示str中第i个字母之后的对应字母出现次数
int[][] suffix=new int[n+1][26];
for(int i=n-1;i>=0;i--){
char c=str.charAt(i);
for(int j=0;j<26;j++){
suffix[i][j]=suffix[i+1][j];
}
suffix[i][c-'a']++;
}
//记录所有"abb"型子序列的个数
long res=0;
for(int i=0;i<n;i++){
char c=str.charAt(i);
for(int j=0;j<26;j++){
//加上当前字母为前缀,所组成的"abb"型子序列的个数
if(j!=c-'a'&&suffix[i][j]>=2){
res+=suffix[i+1][j]*(suffix[i+1][j]-1)/2;
}
}
}
System.out.println(res);
}
}