题目描述

奶牛贝茜在她最喜欢的牧场中发现了一块石碑，上面刻有神秘的碑文。

碑文的文字似乎来自一种神秘的古代语言，可看作一个只包含 C,O,W三种字符的字符串。

尽管贝茜无法解密该文字，但是她很欣赏 C,O,W按顺序构成她最喜欢的单词 COW。

她想知道 COW在碑文中一共出现了多少次。

她不介意 C,O,W之间是否存在其他字符，只要这三个字符按正确的顺序出现即可。

她也不介意多个不同的 COW是否共享了一些字符。

例如，COW在 CWOW 中只出现一次，在 CCOW 中出现两次，在 CCOOWW中出现八次。

给定碑文中的文字，请帮助贝茜计算 COW出现的次数。

样例

输入样例:
6
COOWWW

输出样例:
6

算法1

(模拟法)

字符中只有3个字母,所以可以穷举字符串中的每一个’O’，假设位置i,然后分别计算其左边’C’的个数,
arr1[i]和右边’W’的个数arr2[i],在利用乘法原理进行计数arr1[i]*arr2[i],每次把答案累加到ans中。

时间复杂度

O(3n)
本题输入数据为10^5,所以是可以通过的

参考文献

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long  arr1[N],arr2[N];
int main(){

    string str;
    int n;

    cin>>n;
    cin>>str;

    //从左向右扫描
    long long sum=0;
    for(int i=0;i<n;i++){
        if(str[i]=='C') sum++;
        arr1[i]=sum;
    }
    //从右向左扫描
    sum=0;
    for(int i=n-1;i>=0;i--){
        if(str[i]=='W') sum++;
        arr2[i]=sum;
    }

    //从左向右扫一遍有几个'O'
    long long  res=0;
    for(int i=1;i<n-1;i++){
        if(str[i]=='O'){
            res+=arr1[i-1]*arr2[i+1];
        }
    }
    cout<<res;
    return 0;
}