Идея: пусть dp[i] — минимальная стоимость разрезания первых i символов.

Тогда последний кусок может быть [j, i]:

cpp
dp[i] = min(dp[j - 1] + d(j, i)^2)

Проблема: j слишком много. Но букв всего 26.

Для фиксированного конца i количество разных букв в [j, i] меняется только в местах последних появлений букв.

Например последние позиции разных букв до i такие:

text
10 7 3

Тогда:

text
j = 8..10  -> 1 разная буква
j = 4..7   -> 2 разные буквы
j = 1..3   -> 3 разные буквы

Нам нужно быстро брать минимум dp[j - 1] на таких диапазонах. Для этого используем дерево отрезков.

Код C++17

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

const long long INF = (long long)4e18;

struct SegTree {
    int n;
    vector<long long> tree;

    SegTree(int sz) {
        n = 1;
        while (n < sz) n *= 2;
        tree.assign(2 * n, INF);
    }

    void update(int pos, long long val) {
        pos += n;
        tree[pos] = val;
        pos /= 2;

        while (pos > 0) {
            tree[pos] = min(tree[2 * pos], tree[2 * pos + 1]);
            pos /= 2;
        }
    }

    long long query(int l, int r) {
        if (l > r) return INF;

        l += n;
        r += n;

        long long ans = INF;

        while (l <= r) {
            if (l % 2 == 1) ans = min(ans, tree[l++]);
            if (r % 2 == 0) ans = min(ans, tree[r--]);
            l /= 2;
            r /= 2;
        }

        return ans;
    }
};

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

    int n;
    string s;

    cin >> n >> s;
    s = " " + s;

    vector<long long> dp(n + 1, INF);
    vector<int> last(26, 0);

    SegTree seg(n + 1);

    dp[0] = 0;
    seg.update(0, 0);

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

        vector<int> pos;
        for (int c = 0; c < 26; c++) {
            if (last[c] > 0) {
                pos.push_back(last[c]);
            }
        }

        sort(pos.rbegin(), pos.rend());

        for (int cnt = 1; cnt <= (int)pos.size(); cnt++) {
            int right = pos[cnt - 1];
            int left;

            if (cnt == (int)pos.size()) {
                left = 1;
            } else {
                left = pos[cnt] + 1;
            }

            // j лежит в [left, right]
            // значит dp[j - 1] лежит в [left - 1, right - 1]
            long long bestPrev = seg.query(left - 1, right - 1);

            dp[i] = min(dp[i], bestPrev + 1LL * cnt * cnt);
        }

        seg.update(i, dp[i]);
    }

    cout << dp[n] << '\n';

    return 0;
}

Почему это правильно

Мы перебираем последний отрезок разбиения.

Если последний отрезок — это [j, i], то всё до него уже оптимально посчитано как dp[j - 1].

Стоимость последнего отрезка равна:

cpp
d(j, i) * d(j, i)

Значит формула:

cpp
dp[i] = min(dp[j - 1] + d(j, i)^2)

полностью перебирает все возможные варианты последнего разреза.

Но вместо перебора всех j мы группируем их по одинаковому d(j, i).
Так как букв всего 26, таких групп максимум 26.

Дерево отрезков быстро говорит:

cpp
минимальное dp[j - 1] на нужном диапазоне

Поэтому решение работает быстро.

Сложность

Для каждого i делаем максимум 26 запросов к дереву.

text
O(26 * n * log n)

При n <= 3 * 10^5 это спокойно проходит.