828. Unique Letter String

week9

难度：Hard

题目链接

题目描述

A character is unique in string S if it occurs exactly once in it.

For example, in string S = "LETTER", the only unique characters are "L" and "R".

Let’s define UNIQ(S) as the number of unique characters in string S.

For example, UNIQ("LETTER") = 2.

Given a string S with only uppercases, calculate the sum of UNIQ(substring) over all non-empty substrings of S.

If there are two or more equal substrings at different positions in S, we consider them different.

Since the answer can be very large, return the answer modulo 10 ^ 9 + 7.

Example1:

Input: "ABC"
Output: 10
Explanation: All possible substrings are: "A","B","C","AB","BC" and "ABC".
Evey substring is composed with only unique letters.
Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10

Example2:

Input: "ABA"
Output: 8
Explanation: The same as example 1, except uni("ABA") = 1.

Note: 0 <= S.length <= 10000.

题目分析

  题意是找出一个字符串中的所有子串，再在每个子串中统计所有的只出现一次的字母的个数，最后统计所有的次数之和进行输出。主要是如何找出所有子串且要计算单独出现的字母个数。

解题思路

  如果是按照题目的那种例子来算，算出所有的子串，再判断，那么一定非常复杂，不说子串的数量非常多，判断也是一个大问题，最后还要进行统计，这种方法是不可行的，特别是题目给出的字符串最长有1w个字符。

  既然正向方法不可行，那么可以尝试使用构造的方法，即根据字符串中的每一个字母特殊构造出一个字符串，若该字符串属于字串，则符合+1，因此题目也就转变成了每一个字母包含其的子串有多少个。

  因为有条件限制，且字母的位置固定，因此可以很轻松的判断包含某个字母的子串有多少个，例如A***A**A,这种，若要判断包含中间的A有多少子串，因为有条件限制不能超过1个A，所以就限制在了***A**之中选择，根据排列组合，左边有4种选择，右边有3种选择，所以子串为3*4 = 12。

  因此得到方法：将字母左边的其它字母数*右边其它字母数即为子串数目。

代码

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
class Solution
{
  public:
    int uniqueLetterString(string S)
    {
        vector<int> letter[26];
        for (int i = 0; i < 26; i++)
        {
            letter[i].push_back(-1);
        }
        for (int i = 0; i < S.length(); i++)
        {
            letter[S[i] - 'A'].push_back(i);
        }
        for (int i = 0; i < 26; i++)
        {
            letter[i].push_back(S.length());
        }
        int result = 0;
        for (int i = 0; i < 26; i++)
        {
            for (int j = 1; j < letter[i].size() - 1; j++)
            {
                result += (letter[i][j + 1] - letter[i][j]) * (letter[i][j] - letter[i][j - 1]);
            }
        }
        return result % 1000000007;
    }
};

Note

  1. 考虑到有可能在字符串的边界这种情况，因此将边界考虑在内进行计算，从而更加方便进行计算而无需反复判断，和二分法类似。

  2. 使用了vector数组将不同字母分开，因为这个计算最关键的是找到两边的同种字母和边界来计算出其子串，所以先记录位置再分开计算比较好。

Unique Letter String_test
Unique Letter String_test

最佳解法

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
int uniqueLetterString(string S) {
    int index[26][2], res = 0, N = S.length(), mod = pow(10, 9) + 7;
    memset(index, -1, sizeof(int) * 52);
    for (int i = 0; i < N; ++i) {
        int c = S[i] - 'A';
        res = (res + (i - index[c][1]) * (index[c][1] - index[c][0]) % mod) % mod;
        index[c][0] = index[c][1];
        index[c][1] = i;
    }
    for (int c = 0; c < 26; ++c)
        res = (res + (N - index[c][1]) * (index[c][1] - index[c][0]) % mod) % mod;
    return res;
}

代码分析

  在网上的讨论中发现了一个更加快的代码，这个思路和上面的思路相似，都是计算子串数，不过这个用了边记录边算方法，因为我们每次算只需要知道目标位置以及两边的边界即可，这个就是利用了这一点只记录了上两次同字母的位置，加上第三次就可计算中间的子串数。不过这个做法没有算完，要在最后的时候再加上包含最后字母的子串数。

  这种方法重复利用了空间，减少了遍历的次数，很值得学习。可能有时候这点时间就能决定能不能AC。详细的思路分析

总结

  这道题主要是锻炼我们思考问题时的转化能力，怎么样把问题转化成简单的问题，逆向思路解决。另外如何计算包含某特定位置的子串也是一种值得思考的地方。