AB-string

AB-string

The string t1t2…tk is good if each letter of this string belongs to at least one palindrome of length greater than 1.

A palindrome is a string that reads the same backward as forward. For example, the strings A, BAB, ABBA, BAABBBAAB are palindromes, but the strings AB, ABBBAA, BBBA are not.

Here are some examples of good strings:

• t = AABBB (letters t1, t2 belong to palindrome t1…t2 and letters t3, t4, t5 belong to palindrome t3…t5);
• t = ABAA (letters t1, t2, t3 belong to palindrome t1…t3 and letter t4 belongs to palindrome t3…t4);
• t = AAAAA (all letters belong to palindrome t1…t5);

You are given a string s of length n, consisting of only letters A and B.

You have to calculate the number of good substrings of string s.

Input
The first line contains one integer nn (1≤n≤3⋅10^5) — the length of the string s.

The second line contains the string s, consisting of letters A and B.

Output
Print one integer — the number of good substrings of string s.

Examples
input
5
AABBB
output
6

input
3
AAA
output
3

input
7
AAABABB
output
15

Note
In the first test case there are six good substrings: s1…s2, s1…s4, s1…s5, s3…s4, s3…s5 and s4…s5.

In the second test case there are three good substrings: s1…s2, s1…s3 and s2…s3.

思路：
这道题按照题目意思来判断一个串为符合的，情况比较多，这里我们可以从反面思考一下。不满足的串为ABBBBB…或者BAAAAA…或者…AAAAAB或者…BBBBBA，所以我们可以看到不满足的只有这四种，所以分别从前向后遍历，减掉后面两种，再从后向前，减掉前面两种，最多有n*(n-1)/2。所以就可以得到结果啦~

代码如下：(思路比较巧妙)

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
const int mx=3e5+10;
 
char s[mx];
 
int main(){
 int n,pre=1;
 scanf("%d",&n);
 ll ans=1ll*n*(n-1)/2;
 scanf("%s",s+1);
 for(int i=2;i<=n;i++){
  if(s[i]==s[i-1])
  continue;
  ans++;  //这里先++是因为对于AB我们算了两次(AB和从后向前的BA)
  ans-=i-pre;
  pre=i;
  }
  pre=n;
  for(int i=n-1;i>=1;i--){
  if(s[i]==s[i+1])
  continue;
  ans-=pre-i;
  pre=i;
 }
 printf("%lld\n",ans);
    return 0;
}