7
#yyds干货盘点# 动态规划专题：abb
source link: https://blog.51cto.com/u_15488507/5848569
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# 动态规划专题：abb
精选 原创1.简述：
描述leafee 最近爱上了 abb 型语句，比如“叠词词”、“恶心心”
leafee 拿到了一个只含有小写字母的字符串，她想知道有多少个 "abb" 型的子序列？定义： abb 型字符串满足以下条件：
字符串长度为 3 。
字符串后两位相同。
字符串前两位不同。
输入描述：第一行一个正整数
第二行一个长度为 的字符串（只包含小写字母）
"abb" 型的子序列个数。
示例16
abcbcc
abcbcc
共有1个abb，3个acc，4个bcc
4
abbb
abbb
2.代码实现：
import java.util.*;
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);
}
}
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);
}
}
- 赞
- 收藏
- 评论
- 分享
- 举报
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK