题目描述
给定长度为 n 的字符串 s（只包含字符 r、e、d），定义任何下标 i<j<k 且 s[i]='r', s[j]='e', s[k]='d' 的子序列 “red” 的权值为
|i-j| + |i-k| + |j-k|
计算所有这样的子序列权值之和。
解题思路
题目内容
小红有一个长度为n的字符串s=s1s2⋅⋅.sn，她定义长度为3的子序列sisjsk的权值为∣i−j∣+∣i−k∣+∣j−k∣。
现在，小红希望你计算所有"red"子序列的权值之和。
如果字符串t="red"可以通过删除字符串s中的若干
(可能为零或全部)元素得到，则字符串t是字符串s的"red"子序列。
输入描述
第一行输入一个整数n(1≤n≤2×105)，表示字符串的长度。
第二行输入一个长度为n，且只由'r'、'e'、'd'三个小写字母组成的字符串
输出描述
在一行上输出一个整数，代表所有"red"子序列的权值之和。
样例1
输入
4
reed
输出
12
说明
在该样例中，一共有两个不同的"red"子序列:
删除第二个字符得到的子序列S1S3S4权值为
∣1−3∣+∣1−4∣+∣3−4∣=6;
删除第三个字符得到的子序列S1S2S4权值为
∣1−2∣+∣1−4∣+∣2−4∣=6。
样例2
输入
7
redeeed
输出
52
