首页 > 试题广场 >

abb

[编程题]abb
  • 热度指数：6896 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
leafee 最近爱上了 abb 型语句，比如“叠词词”、“恶心心”

leafee 拿到了一个只含有小写字母的字符串，她想知道有多少个 "abb" 型的子序列？
定义： abb 型字符串满足以下条件：

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


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



输出描述:
"abb" 型的子序列个数。
示例1

输入

6
abcbcc

输出

8

说明

共有1个abb，3个acc，4个bcc
示例2

输入

4
abbb

输出

3
算法知识视频讲解
添加回答
Java
OkayPlus头像 OkayPlus
debug了半天，结果是因为超过int范围了。。。
发表于 2022-04-10 20:25:26 回复(1)
牛客799683366号头像 牛客799683366号
解题思路：
由于题目要求的为子序列而非子串，因此对于一个特定位置的字符，其与后面字符的有序排列组合均为符合条件的子序列

举例：对于字符串abbbb，选定字符a，a可与后面4个b中的任意2个搭配形成abb，因此有6种方案

对于整个字符串，可事先统计好字符出现频次，而后在遍历的过程中对每个字符进行计算。在遍历的过程中，由于字符出现的次数已事先统计，直接取值计算即可

下面上代码 
import math
from collections import defaultdict

def solution(n, string):
    # 初始化一个字典用于记录每个字符出现的次数
    d = defaultdict(int)
    # 统计次数
    for s in string:
        d[s] += 1
    
    # 解的数量
    num = 0
    # 开始遍历
    for s in string:
        # 每过一个字符，对应统计减一
        d[s] -= 1
        # 遍历，对于当前字符，与其他字符的排列组合数目即为潜在的abb序列数目
        for e in d.keys():
            if e != s:
                num += math.comb(d[e], 2)
    
    return num

if __name__ == "__main__":
    while True:
        try:
            t = int(input())
            string = input()
            print(solution(t, string))
        except EOFError:
            break


发表于 2021-11-11 13:41:12 回复(0)
C++
牛客288355985号头像 牛客288355985号
逆序累计组合数 
#include<iostream>
using namespace std;

int num[128]={};
char str[100009];

long long Cn2(long long n){
  return n*(n-1)/2;
}

int main(){
  int n;
  cin>>n>>str;
  long long result=0;
  for(int i=n-1;i>=0;i--){
    for(int j='a';j<='z';j++){
      if(j!=str[i]){
        result+=Cn2(num[j]);
      }
    }
    num[str[i]]++;
  }
  cout<<result<<endl;
}


发表于 2022-09-01 11:48:36 回复(0)
C++
MechaVX头像 MechaVX
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    string str;
    cin >> str;
    int arr[26]{};
    int count[26]{};
    long long result = 0;
    int index;
    for (int i = 0; i < n; ++i) {
        index = str[i] - 'a';
        result += arr[index];
        arr[index] += i - count[index]++;
    }
    cout << result << endl;
    return 0;
}
    /*
    先说明count数组记录的是某个字母之前出现的次数（应该也能够明白index=str[i]-'a'是干什么的）。
    以字符串zabcdectca为例
    分析叠词字母为c的 _cc 情况，此时index='c'-'a'=2，
    c字母的下标索引为3 6 8

    先直接快进>> 到当i=6时，该位置的c可以怎样构成叠词？
    可以与3位置的c和3位置前面不为c的字母一起组成叠词，

   
    那么此时以3号位置的c为叠词的第二个字母，总共可以增多arr['c'-'a']，即arr[2]个叠词，即result+=arr[2]。
    其中这个arr[2]表示什么后面会说明。

    未雨绸缪地想，当走到位置8的字母c时，_cc 形式的叠词可以增加多少个？
    它可以与位置3的c为叠词的第二个字母，以及3号位置前面不是c的字母组合，
    或者与位置6的c作为叠词的第二个字母，以及6号位置前面不是c的字母组合，
    对于前者那就是像之前那样增加arr[2]。
    对于后者，那就是6号位置前面有多少个不是c的字母，
    因为用count数组记录了某个字母之前出现过的次数（这里的之前是指6号位置之前，即此时count[2]=1），
    一轮分析过后前面不是c的字母应该有i-count[2]个。

    因而下次再次碰到c时，该形式的叠词会增加arr[2] + (i-count[2])个。
    所以直接arr[2]+=i-count[2]，这个arr数组就是这么来的。

    做好了将来的打算了，接下来就是应该++count[2]。

    至于第一次碰到c的时候好像构不成叠词也result+=arr[index]了，因为此时arr[index]值是0，不影响结果

    大致就是这么回事，感觉不太好解释。


    */
发表于 2021-12-30 23:13:33 回复(0)
C++
牛客723296405号头像 牛客723296405号
不太清楚怎么用动态 规。直观解法：存储好各个字符的个数，逐个遍历其它大于2的字符个数取Cn2 ，然后从map中计数减一或者删除已经使用的元素。

 long long n = 0;
    cin >> n;
    string str = "";
    cin >> str;
    long long  tc = 0;
    map<char,int> cm;
     for (long long i =  0; i < n; i++)
     {
         cm[str.at(i)]++;
     }
    for (long long i =  0; i < n; i++)
    {
         for (auto itor = cm.begin(); itor != cm.end(); ++itor)
         {
            if (itor->second >= 2 && itor->first != str.at(i))
            {
                tc += f(itor->second);
            }
         }
        if (cm[str.at(i)] > 2)
        {
            cm[str.at(i)]--;
        }
        else
        {
            cm.erase(str.at(i));
        }       
    }
    cout << tc;
发表于 2021-11-29 22:05:06 回复(0)
C++
鸢尾零音头像 鸢尾零音
对于形如 abb 的字符，拆分为三部分 left、mid、right，遍历中间字符 mid，查找前方有多少字符与 mid 不同，后方有多少字符与 mid 相同，两者相乘即为以 mid 为中间字符的结果数量。 
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    vector<long long> diff(n), same(n);
    vector<long long> cnt(26);
    for (int i = 0; i < n; i++) {
        diff[i] = i - cnt[s[i] - 'a'];
        cnt[s[i] - 'a']++;
    }
    cnt = vector<long long>(26, 0);
    for (int i = n - 1; i >= 0; i--){
        same[i] = cnt[s[i] - 'a'];
        cnt[s[i] - 'a']++;
    }
    long long res = 0;
    for (int i = 0; i < n; i++) {
        res += diff[i] * same[i];
    }
    cout << res << endl;

    return 0;
}
// 64 位输出请用 printf("%lld")9


发表于 2025-03-27 14:09:51 回复(0)
Python3
牛客770400571号头像 牛客770400571号 
n = int(input())
s = input()
ans = 0
arr1, arr2 = [0]*26, [0]*26
for alpha in s[::-1]:
    index = ord(alpha) - 97
    ans += sum(arr2) - arr2[index]
    arr2[index] += arr1[index]
    arr1[index] += 1
print(ans)

发表于 2025-03-05 10:36:57 回复(0)
C++
牛客644666460号头像 牛客644666460号
#include <string>
#include<iostream>
using namespace std;

int main() {
    int sum=0;
    int x;
    cin>>x;
    string a;
    cin>>a;
    if(x<3){
        cout<<sum;
        return 0;
    }
    for(size_t i=0;i<a.length()-2;++i){
        for(size_t j=i+1;j<a.length()-1;++j){
            for(size_t k=j+1;k<a.length();++k){
                if(a[i]!=a[j]&&a[i]!=a[k]&&a[j]==a[k]){
                    sum++;
                }
            }
        }
    }
    cout<<sum;
    return 0;
}
不知道为啥第8组实例通过不了

发表于 2024-12-09 21:15:39 回复(0)
C
cs小白_头像 cs小白_ 
#include <stdio.h>

int main() {
    int n;
    scanf("%d",&n);
    char c[n];
    getchar();
    scanf("%s",c);
    int sum[n+1][26];
    for (int i=0; i<n+1; i++) {
        for (int j=0; j<26; j++) {
             sum[i][j]=0;
           }
    }
    // for (int i=0; i<n; i++) {
    //     for (int j=i; j<n; j++) {
    //          sum[i][c[j]-'a']++;
    //        }
    // }
    for(int i=n-1;i>=0;i--){
        for(int j=0;j<26;j++)sum[i][j]=sum[i+1][j];
        sum[i][c[i]-'a']++;
    }
    long long r=0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<26; j++) {
             if (j!=(c[i]-'a')) {
                    r+=(sum[i][j]*(sum[i][j]-1)/2);
             }
           }
    }
   
        printf("%lld", r);
    
    return 0;
}

#include <stdio.h>

int main() {
    int n;
    scanf("%d",&n);
    char c[n];
    getchar();
    scanf("%s",c);
    int sum[n+1][26];
    for (int i=0; i<n+1; i++) {
        for (int j=0; j<26; j++) {
             sum[i][j]=0;
           }
    }
    // for (int i=0; i<n; i++) {
    //     for (int j=i; j<n; j++) {
    //          sum[i][c[j]-'a']++;
    //        }
    // }
    for(int i=n-1;i>=0;i--){
        for(int j=0;j<26;j++)sum[i][j]=sum[i+1][j];
        sum[i][c[i]-'a']++;
    }
    long long r=0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<26; j++) {
             if (j!=(c[i]-'a')) {
                    r+=(sum[i][j]*(sum[i][j]-1)/2);
             }
           }
    }
   
        printf("%lld", r);
    
    return 0;
}

发表于 2024-12-01 14:30:31 回复(0)
abc222头像 abc222 
#include <bits/stdc++.h>
using namespace std;
#define LL long long
int main() {
    int n;
    LL ans = 0;
    cin >> n;
    string s;
    cin >> s;
    unordered_map<char, long long> mp;
    for(auto &ch : s){
        mp[ch]++;
    }
    for(auto &ch : s){
        if(mp.count(ch)) mp[ch]--;
        if(mp[ch] == 0) mp.erase(ch);
        for(auto &pr : mp){
            LL t = pr.second;
            if(pr.first != ch) ans += (t * (t-1)) / 2;
        }   
    }
    cout << ans;
}
STL
发表于 2024-10-29 21:15:51 回复(0)
双非阴沟老鼠找工作头像 双非阴沟老鼠找工作 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin>>n;
    string str;
    cin>>str;
    long long res=0;
    // 字母i 的出现个数
    int a[26] = {0};
    for(int i=n-1;i>=0;i--){
        // a-z出现的次数
        for(int j=0;j<26;j++){
            if (j !=str[i] - 'a') {
                res += 1ll * a[j] * (a[j] - 1) / 2;
            }
        }
        a[str[i] - 'a'] ++;
    }

    cout << res << "\n";
    
}
// 64 位输出请用 printf("%lld")

发表于 2024-08-13 22:27:00 回复(0)
dijs_sdd头像 dijs_sdd
import java.util.Scanner;

public class Main {
    private static int Combination(int n, int k) {
        int a=1,b=1;
        if(k>n/2) {
            k=n-k;
        }
        for(int i=1;i<=k;i++) {
            a*=(n+1-i);
            b*=i;
        }
        return a/b;
    }
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        String str= scan.next();
        char[] s=str.toCharArray();
        int[] pre=new int[26];
        long ans=0;
        for(int i=0;i<n;i++){
            pre[s[i]-'a']++;
        }
        for(int i=0;i<n;i++){
            pre[s[i]-'a']--;
            for(int j=0;j<26;j++){
                if(pre[j]==0||(s[i]-'a')==j){
                    continue;
                }
                if(pre[j]>=2){
                   ans+=Combination(pre[j],2);
                }
            }
        }
        System.out.println(ans);
    }
}

发表于 2024-05-30 19:09:02 回复(0)
愉快的大白菜不讲武德头像 愉快的大白菜不讲武德 
    static void DP36() {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        HashMap<Character, ArrayList<Integer>> map = new HashMap<>();
        String s = in.next();
        for (int i = 0; i < n; i++) {
            Character C = s.charAt(i);
            if (map.containsKey(C)) map.get(C).add(i);
            else {
                ArrayList<Integer> arr = new ArrayList<>();
                arr.add(i);
                map.put(C, arr);
            }
        }

        long max = 0;
        for (char c = 'a'; c <= 'z'; c++) {
            max += getCountAbb(map, c);
        }
        System.out.println(max);
    }

    private static long getCountAbb(HashMap<Character, ArrayList<Integer>> map, Character C) {
        if (!map.containsKey(C) || map.get(C).size() == 1) return 0;
        ArrayList<Integer> arr = map.get(C);
        long max = 0;
        int n = arr.size();

        for (int i = 0; i < n - 1; i++) {
            int index = arr.get(i); //字母所在的 位置.
            max += (long) (index - i) * (n - 1 - i); //前面字母的个数个数,除去已有的. 乘后面字母的数量
        }
        return max;
    }

发表于 2022-11-19 20:56:48 回复(0)
C++
openallzzz头像 openallzzz 
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

typedef long long LL;

int n;
char s[N];
int cnt[N][26];

int main()
{
    scanf("%d", &n);
    scanf("%s", s + 1);
    
    for(int i = n; i >= 1; i --) {
        for(int j = 0; j < 26; j ++)
            cnt[i][j] = cnt[i + 1][j] + ((s[i] - 'a' == j) ? 1 : 0);
    }
    
    LL res = 0;
    for(int i = 1; i < n; i ++)
    {
        for(int j = 0; j < 26; j ++)
        {
            if(j != s[i] - 'a')
            {
                if(cnt[i + 1][j] >= 2) res += (cnt[i + 1][j]) * 1LL * (cnt[i + 1][j] - 1) / 2;
            }
        }
    }
    printf("%ld\n", res);
    return 0;
}

发表于 2022-07-19 16:53:00 回复(0)
Java
逆风飞翔的猪头像 逆风飞翔的猪 
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            String str = in.next();
            int[][] dp = new int[n + 1][26];
            Arrays.fill(dp[n], 0);
            for (int i = n - 1; i >= 1; i--) {
                char ch = str.charAt(i);
                for (int j = 0; j < 26; j++) {
                    if (ch - 'a' == j) {
                        dp[i][j] = dp[i + 1][j] + 1;
                    } else {
                        dp[i][j] = dp[i + 1][j];
                    }
                }
            }
            long res = 0;
            for (int i = 1; i <= n; i++) {
                char c = str.charAt(i - 1);
                for (int j = 0; j < 26; j++) {
                    if (c - 'a' != j && dp[i][j] >= 2) {
                        res += dp[i][j] * (dp[i][j] - 1) / 2;
                    }
                }
            }
            System.out.println(res);
        }
    }
}

发表于 2022-06-25 17:01:41 回复(0)
提交观点

问题信息

难度：
15条回答 2513浏览

热门推荐

通过挑战的用户

查看代码

相关试题

abb

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号