牛客算法心得—

牛客算法心得——abb（dp）

大家好，我是晴天学长，传智杯的题，我准备写一个题解，需要的小伙伴可以关注支持一下哦！后续会继续更新的。💪💪💪

1) .abb

在这里插入图片描述
leafee 最近爱上了 abb 型语句，比如“叠词词”、“恶心心”
leafee 拿到了一个只含有小写字母的字符串，她想知道有多少个 "abb" 型的子序列？
定义： abb 型字符串满足以下条件：

字符串长度为 3 。
字符串后两位相同。
字符串前两位不同。

输入描述：
第一行一个正整数 n
第二行一个长度为 n 的字符串（只包含小写字母）

输出描述：
"abb" 型的子序列个数。
示例1
输入：
6
abcbcc
输出：
8
说明：
共有1个abb，3个acc，4个bcc

示例2
输入：
4
abbb
输出：
3

2) .算法思路

abb（反面动规）
1.用一个一维数组维护就行。
2.从后面遍历
3. 与其他字母组合，不包括自己

ans = t（t-1） / 2 ；

3）算法步骤

1.使用一个int数组word记录每个字母在字符串s中出现的次数。

2.从字符串s的尾部开始遍历,得到每个字母,计算下标,将对应word数组位置+1。

3.对每个字母统计后,再次遍历word数组。

4.对每个字母i,遍历其他字母j。

5.如果j位置的word值大于等于2,计算它的组合数word[j]*(word[j]-1)/2 ,即该字母出现次数的选择2个的组合数。

6.将所有字母j的组合数加到总和sum中。

7.最终sum就是字符串s中每个字母出现次数的组合数之和。

4）. 代码实例

import java.io.*;public class Main {static int[] word = new int[26];static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static String[] lines;public static void main(String[] args) throws IOException {lines = in.readLine().split(" ");int n = Integer.parseInt(lines[0]);lines = in.readLine().split(" ");String s = lines[0];int length = s.length();long sum = 0;for (int i = length - 1; i >= 0; i--) {char temp = s.charAt(i);int index = temp - 'a';for (int j = 0; j < 26; j++) {if (j != index && word[j] >= 2) {sum += (long) word[j] *(word[j]-1)/2;}}word[index]++;}System.out.println(sum);}
}