# [Editorial] AB-string

## Đề bài
The string $t_1t_2...t_k$ 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 $t_1$, $t_2$ belong to palindrome $t_1...t_2$ and letters $t_3$, $t_4$, $t_5$ belong to palindrome $t_3...t_5$ );
* $t$ = $ABAA$ (letters $t_1$, $t_2$, $t_3$ belong to palindrome $t_1...t_3$ and letter $t_4$ belongs to palindrome $t_3...t_4$ );
* $t$ = $AAAAA$ (all letters belong to palindrome $t_1...t_5$ );

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$.

[Link bài trên Codeforces](https://codeforces.com/problemset/problem/1238/D)

## Tóm tắt

Tìm số xâu con của $s$ thõa mãn: tất cả chữ cái của nó thuộc một palindrome độ dài > 1.

## Rằng buộc

$1 <= n <= 3.10^5$

## Lời giải

Thay vì tính số các xâu con thỏa mãn, ta sẽ tính số các xâu con độ dài > 1 $n (n-1)/2$ và số xâu con không thỏa mãn $bad$, khi đó thì đáp số sẽ là $n(n-1)/2 - bad$.

Xét xâu $t = t_1t_2...t_k$ , coi một chữ cái $t_i$ là "tốt" nếu nó thuộc một palindrome trong $t$.

Có thể thấy rằng tất cả chữ cái từ $t_2...t_{k-1}$ đều "tốt" vì:

* nếu $t_i = t_{i-1}$ hoặc $t_i = t_{i+1}$ thì $t_i$ thuộc palindrome độ dài = 2 (dạng $AA$ hoặc $BB$ )
* nếu $t_i \neq t_{i-1}$ và $t_i \neq t_{i+1}$ thì $t_i$ sẽ thuộc palindrome $t_{i-1}t_it_{i+1}$ (dạng $ABA$ hoặc $BAB$ )

Như vậy chỉ có chữ cái $t_1$ và $t_k$ là có thể không "tốt".

Từ đó ta có dạng của những xâu không tốt:
* $ABB...BB$
* $BB...BBA$
* $BAA...AA$
* $AA...AAB$

## Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    long long n;
    string s;
    cin >> n >> s;

    long long ans = n * (n - 1) / 2; // all substrings len >= 2
    long long bad = 0; // bad ones

    for(int times = 0; times < 2; times++) {
        long long cur = 1;
        for(int i = 1; i < n; i++) {
            if(s[i] == s[i - 1]) {
                cur++;
            } else {
                bad += cur - times; // subtract overlapping part
                cur = 1;
            }
        }
        reverse(s.begin(), s.end());
    }

    cout << ans - bad << '\n';
}

*Nguyễn Hoàng Dũng 2021-09-19*