Luobuyu's Blog

0%

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

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 2.3k 阅读时长 ≈ 2 分钟
考虑每个数字的贡献，或者考虑dp，注意与之前周赛题目的区别。

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

题目描述：

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

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

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

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

数据范围：

$1\le s.len \le 10^5$

$s$ 只包含大写字母。

题解：

dp：

考虑 $dp[i]$ 表示所有以 $i$ 结尾的子字符串的分数。 $dp[i]$ 可以看做 $dp[i-1]$ 的基础之上加上 $s[i]$ ，需要考虑加上 $s[i]$ 之后 $dp[i-1]$ 是怎样变化的。

2916. 子数组不同元素数目的平方和 II 跟这个题目比较类似，但是变化有点不一样。

假设原字符串为 PQABCADE，需要在该字符串的基础之上加上s[i]='A'。注意到子串 A,EA,DEA 都会增加 $1$ ，而子串 ADE,CADE,BCADE 都会减少 $1$ 。因此需要记录 $s[i]$ 前一个的位置 $pre1[i]$ ，以及前前一个的位置 $pre2[i]$ 。状态转移方程就为

可以把 $pre1[i], pre2[i]$ 初始化为 $-1$ ，这样的话就统一起来了。

因为这个题目只需要进行区间加，而且只需要记录总数就行了，不用知道每个区间里面都是什么。不像上面那个题目，那个求平方和，需要知道区间内元素的平方和以及元素的和，需要在原来的基础之上加上 $len \times k^2 + 2k\times \sum a_i$ ，不仅需要维护区间平方和=，还要维护区间和。该题只需要维护区间和，所以能够通过状态转移过来，而另一个题目需要使用线段树维护。

当然这个也可以使用线段树维护，但是比较浪费，时间比较慢。

计数原理：

统计每一个 $s[i]$ 对答案的共线，即每个 $s[i]$ 可以作为多少个子数组的唯一元素。

可以预处理出 $left[i]$ 和 $right[i]$ 分别代表 $s[i]$ 作为子数组唯一字符时，能到达的最远的下标。

则子数组左端点有 $i - left[i]$ 个，右端点有 $right[i] - i$ 个，子数组个数就为二者的乘积。

预处理的时候可以使用 $left\_ch[26]$ 表示到达当前下标时每个字符的前一个。

代码：

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
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    int uniqueLetterString(string s)
    {
        int n = s.length();
        // pre1 前一个， pre2 前前一个
        vector<int> pre1(26, -1), pre2(26, -1);

        long long sum = 0;
        long long cur = 0;
        for (int i = 0; i < n; ++i)
        {
            cur += i - pre1[s[i] - 'A'];
            cur -= pre1[s[i] - 'A'] - pre2[s[i] - 'A'];
            sum += cur;
            pre2[s[i] - 'A'] = pre1[s[i] - 'A'];
            pre1[s[i] - 'A'] = i;
        }
        return sum;
    }
};
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
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    int uniqueLetterString(string s)
    {
        int n = s.length();
        vector<int> left(n), right(n);
        vector<int> left_ch(26, -1), right_ch(26, n);
        for (int i = 0; i < n; ++i)
        {
            left[i] = left_ch[s[i] - 'A'];
            left_ch[s[i] - 'A'] = i;
        }
        for (int i = n - 1; i >= 0; --i)
        {
            right[i] = right_ch[s[i] - 'A'];
            right_ch[s[i] - 'A'] = i;
        }
        int ans = 0;
        for (int i = 0; i < n; ++i)
        {
            ans += (i - left[i]) * (right[i] - i);
        }
        return ans;
    }
};