1. Mô tả bài toán

Cho một xâu S, ta định nghĩa độ điểm f(S) là số ký tự xuất hiện đúng một lần trong xâu đó.

Ví dụ: f("aba") = 1, f("abc") = 3, f("aaa") = 0.

Cho xâu S độ dài n (chỉ gồm chữ cái thường), yêu cầu tính tổng của f(S[i..j]) cho tất cả các xâu con không rỗng của S.

Input: Một dòng duy nhất là xâu S (1 ≤ n ≤ 100000).

Output: Một số nguyên là tổng cần tìm.

Ví dụ: S = "ababc" → output = 21.

2. Phân tích

Phương pháp vét cạn O(n²) chỉ chạy được với n ≤ 1000. Để đạt O(n), ta cần xét đóng góp của từng ký tự riêng lẻ.

Xét ký tự c tại vị trí i. Nó chỉ đóng góp 1 điểm cho các xâu con mà trong xâu đó chỉ có duy nhất một ký tự c (tức là không có ký tự c nào khác).

Gọi vị trí xuất hiện trước của cùng ký tự đó là L, vị trí xuất hiện sau là R (nếu không có trước thì L=0, không có sau thì R=n+1). Khi đó, mọi xâu con bắt đầu từ vị trí trong (L, i] và kết thúc trong [i, R) sẽ chỉ chứa đúng một ký tự c.

Số lượng xâu con như vậy là (i - L) * (R - i).

Tổng đáp số = Σ cho tất cả vị trí i.

3. Cài đặt (C++)

3.1. Thuật toán vét cạn (chạy trong 50% test)

#include <iostream>
#include <string>
#include <vector>
using namespace std;
using ll = long long;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        vector<int> cnt(26, 0);
        int distinct = 0;          // số ký tự xuất hiện đúng 1 lần trong xâu con hiện tại
        for (int j = i; j < n; ++j) {
            int idx = s[j] - 'a';
            cnt[idx]++;
            if (cnt[idx] == 1) distinct++;
            else if (cnt[idx] == 2) distinct--;
            ans += distinct;
        }
    }
    cout << ans;
    return 0;
}

3.2. Thuật toán tối ưu O(n)

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
using ll = long long;

const int MAXN = 100005;

int main() {
    string s;
    cin >> s;
    int n = s.size();

    // left[i] = vị trí xuất hiện trước của ký tự s[i] (tính từ 1)
    // right[i] = vị trí xuất hiện sau
    vector<int> left(n+2, 0), right(n+2, n+1);
    int last[26];
    memset(last, 0, sizeof(last));

    for (int i = 1; i <= n; ++i) {
        int ch = s[i-1] - 'a';
        left[i] = last[ch];
        last[ch] = i;
    }

    for (int i = 0; i < 26; ++i) last[i] = n+1;
    for (int i = n; i >= 1; --i) {
        int ch = s[i-1] - 'a';
        right[i] = last[ch];
        last[ch] = i;
    }

    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += (ll)(i - left[i]) * (right[i] - i);
    }

    cout << ans;
    return 0;
}

4. Giải thích code tối ưu

Mảng left và right lưu vị trí gần nhất bên trái và bên phải của cùng một ký tự. Với ký tự đầu tiên, left = 0; với ký tự cuối, right = n+1.

Công thức (i - left[i]) * (right[i] - i) cho số xâu con mà ký tự tại i là ký tự xuất hiện duy nhất.

Độ phức tạp: O(n) thời gian, O(n) bộ nhớ.