题目

本质都是DP

DP

cpp
class Solution {
public:
    int uniqueLetterString(string s) {
         vector<vector<int>> d(26, {-1});
        for (int i = 0; i < s.size(); ++i) {
            d[s[i] - 'A'].push_back(i);
        }
        int ans = 0;
        for (auto& v : d) {
            v.push_back(s.size());
            for (int i = 1; i < v.size() - 1; ++i) {
                ans += (v[i] - v[i - 1]) * (v[i + 1] - v[i]);
            }
        }
        return ans;

    }
};

使用map

cpp
class Solution {
public:
    int uniqueLetterString(string s) {
 unordered_map<char, vector<int>> indies;
    for (int i = 0; i < s.length(); i++) {
        char c = s[i];
        if (!indies.count(c)) {
            indies[c] = { -1 };
        }
        indies[c].push_back(i);
    }
    int res = 0;
    for (auto& entry : indies) {
        entry.second.push_back(s.length());
        for (int i = 1; i < entry.second.size() - 1; i++) {
            int left = entry.second[i] - entry.second[i - 1];
            int right = entry.second[i + 1] - entry.second[i];
            res += left * right;
        }
    }
    return res;
    }
};