Subtask #1

• Nhận thấy ~S~ nhỏ nên ta chỉ cần duyệt mọi xâu con trong xâu ~S~, nếu ~S~ là xâu con lí tưởng thì cộng kết quả lên ~1~.
• Độ phức tạp: ~O(n^3)~

Subtask #2

• Nhận xét: Giữa ~2~ kí tự giống nhau chỉ tồn tại tối đa ~1~ xâu con lí tưởng. Vì vậy, ta chỉ cần duyệt qua các kí tự từ ~a~ đến ~z~. Nếu giữa 2 kí tự giống nhau gần nhất chỉ có một loại kí tự khác với kí tự đó, cộng kết quả lên ~1~.
• Độ phức tạp: ~O(26 \times n)~.

Code mẫu

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/

#include <bits/stdc++.h>

#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back

/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/

const long double PI = 3.1415926535897932384626433832795;
const int INF = 1000000000000000000;
const int MOD = 1000000007;
const int MOD2 = 1000000009;
const long double EPS = 1e-6;

using namespace std;

string s;
int n, res, dp[100005];

signed main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> s;
    n = sz(s);

    for1(i,0,n - 2) if (s[i] == s[i + 1]) res++;

    for1(i,1,n - 1) {
        if (s[i] == s[i - 1]) dp[i] = dp[i - 1] + 1;
        else dp[i] = 0;
        // cout << dp[i] << "\n";
    }

    for1(i,1,n - 2) {
        if (i - dp[i] > 0 && s[i - dp[i] - 1] != s[i] && s[i - dp[i] - 1] == s[i + 1]) res++;
    }

    cout << res;

}