子串分值

最暴力做法 $O(n^3)$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;

int main()
{
    string str;
    cin >> str;

    int res = 0;
    for (int l = 0; l < str.size(); ++ l )
        for (int r = l; r < str.size(); ++ r )
        {
            unordered_set<char> S, T;
            for (int i = l; i <= r; ++ i )
            {
                char c = str[i];
                if (!S.count(c) && !T.count(c))
                    S.insert(c);
                else if (S.count(c))
                    S.erase(c), T.insert(c);
            }
            res += S.size();
        }

    cout << res << endl;

    return 0;
}

优化一维 $O(n^2)$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;

int main()
{
    string str;
    cin >> str;

    int res = 0;
    for (int l = 0; l < str.size(); ++ l )
    {
        unordered_set<char> S, T;
        for (int i = l; i < str.size(); ++ i )
        {
            char c = str[i];
            if (!S.count(c) && !T.count(c))
                S.insert(c);
            else if (S.count(c))
                S.erase(c), T.insert(c);
            res += S.size();
        }
    }

    cout << res << endl;

    return 0;
}