技术学习分享_CKX技术 技术资讯 #yyds干货盘点# 动态规划专题:abb

#yyds干货盘点# 动态规划专题:abb

广告位

1.简述:

描述

leafee 最近爱上了 abb 型语句,比如“叠词词”、“恶心心”

leafee 拿到了一个只含有小写字母的字符串,她想知道有多少个 “abb” 型的子序列?定义: abb 型字符串满足以下条件:

字符串长度为 3 。

字符串后两位相同。

字符串前两位不同。

输入描述:

第一行一个正整数 #yyds干货盘点# 动态规划专题:abb

第二行一个长度为 #yyds干货盘点# 动态规划专题:abb 的字符串(只包含小写字母)

#yyds干货盘点# 动态规划专题:abb

输出描述:

“abb” 型的子序列个数。

示例1

输入:

6
abcbcc

输出:

8

说明:

共有1个abb,3个acc,4个bcc

示例2

输入:

4
abbb

输出:

3

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);
}
}
本文来自网络,不代表技术学习分享_CKX技术立场,转载请注明出处。

作者: CKX技术

上一篇
下一篇
广告位

发表回复

返回顶部