828.统计子串中的唯一字符

链接：828.统计子串中的唯一字符
难度：Hard
标签：哈希表、字符串、动态规划
简介：给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。

题解 1 - cpp

• 编辑时间：2022-09-06
• 执行用时：52ms
• 内存消耗：36MB
• 编程语言：cpp
• 解法介绍：记录每个字符出现的下标，统计每个字符只出现一次的子串。

class Solution {
public:
    int uniqueLetterString(string s) {
        unordered_map<char, vector<int>> m;
        for (int i = 0; i < s.size(); i++) m[s[i]].push_back(i);
        int ans = 0;
        for (auto &item : m) {
            vector<int> list = item.second;
            list.insert(list.begin(), -1);
            list.push_back(s.size());
            for (int i = 1; i < list.size() - 1; i++) ans += (list[i] - list[i - 1]) * (list[i + 1] - list[i]);
        }
        return ans;
    }
};

题解 2 - python

• 编辑时间：2023-11-26
• 执行用时：272ms
• 内存消耗：20.83MB
• 编程语言：python
• 解法介绍：按字符归类所有下标，记录当前字符下标仅出现一次的频率。

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        n = len(s)
        ans = 0
        clist = [[-1] for _ in range(26)]
        for i in range(n): clist[ord(s[i]) - ord('A')].append(i)
        for arr in clist:
            arr.append(n)
            for j in range(1, len(arr) - 1):
                ans += (arr[j] - arr[j - 1]) * (arr[j + 1] - arr[j])
        return ans