统计子串中的唯一字符

Category Difficulty Likes Dislikes
algorithms Hard (55.73%) 243 -
Tags

math

Companies

Unknown

我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。

例如：s = "LEETCODE" ，则其中 "L", "T","C","O","D" 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5 。

本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。输入用例保证返回值为 32 位整数。

注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。

示例 1：

1
2
3
4
5
输入: s = "ABC"
输出: 10
解释: 所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。
     其中，每一个子串都由独特字符构成。
     所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10

示例 2：

1
2
3
输入: s = "ABA"
输出: 8
解释: 除了 countUniqueChars("ABA") = 1 之外，其余与示例 1 相同。

示例 3：

1
2
输入：s = "LEETCODE"
输出：92

提示：

  • 1 <= s.length <= 10^5
  • s 只包含大写英文字符

代码

求出每一种组合类型中唯一字符的值叠加（c++）

因为需要不断通过字符串去得到值，效率很低，不通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/*
 * @lc app=leetcode.cn id=828 lang=cpp
 *
 * [828] 统计子串中的唯一字符
 */

// @lc code=start
class Solution {
public:
    void strSort(string& s, int lt, int rt) {
        if (lt >= rt) return ;
        int i = lt, j = rt;
        int index = s[lt] - '0';
        while (i < j) {
            while (i < j && s[j] - '0' >= index) --j;
            while (i < j && s[i] - '0' <= index) ++i;
            if (i < j) {
                char tmp = s[i];
                s[i] = s[j];
                s[j] = tmp;
            }
        }
        s[lt] = s[i];
        s[i] = (char)(index + '0');
        strSort(s, lt, i - 1);
        strSort(s, i + 1, rt);
    }

    int uniqueLetterString(string s) {
        int len = s.size();
        int n = 1, res = 0;
        unordered_set<string> st;
        /** 
         * 1: a b c     3
         * 2: ab bc     4
         * 3: abc       3
         * res = 3 + 4 + 3
         */
         // 5 + 7 + 6 + 5 + 3
        for (n = 1; n <= len; ++n) {
            for (int i = 0; i <= len-n; ++i) {
                // st.insert(s.substr(i, n));
                res += countUniqueChars(s.substr(i, n));
            }
            // for (auto e : st) {
                // res += countUniqueChars(e);
            // }
            // st.clear();
        }
       return res;
        // return countUniqueChars("LEETCODESBAT");
        // return countUniqueChars(s);
    }
    int countUniqueChars(string s) {
        int res = 0, len = s.size();
        if (len == 1) return 1;
        strSort(s, 0, len-1);
        unordered_set<char> st;
        for (int i = 0; i < len-1; ++i) {
            if (st.count(s[i]) == 0 && s[i + 1] != s[i]) {
                st.insert(s[i]);
                ++res;
            } else if (st.count(s[i]) == 0) {
                st.insert(s[i]);
            }
        }
        if (len >= 2 && s[len-1] != s[len-2]) ++res;
        // if (len >= 2 && 'L' != 'L') ++res;
        return res;
    }
};
// @lc code=end

分别计算每个字符的贡献

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int uniqueLetterString(string s) {
        unordered_map<char, vector<int>> mp;
        int len = s.size(), res = 0;
        
        /**
         * b = 字符x出现的第b次，a = b-1次，c = b + 1次
         * 每个字符的贡献为 for { (b - a) * (c - b) }
         * 首位分别添加-1和s.size()来辅助计算
         */
        for (int i = 0; i < len; ++i) {
            mp[s[i]].emplace_back(i);
        }
        for (auto &&[_, arr]: mp) {
            arr.insert(arr.begin(), -1);
            arr.emplace_back(len);
            for (int i = 1; i < arr.size() - 1; ++i) {
                res += (arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i]);
            }
        }
        return res;
    }
};