【leetcode】【2022/9/6】828. 统计子串中的唯一字符

问题描述：

• 我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。
  • 例如：s = "LEETCODE"，则其中 "L","T","C","O","D" 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5。
  • s 只包含大写英文字符。
• 本题将会给你一个字符串 s，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。
• 注意，某些子字符串可能是重复的，但统计时也必须算上这些重复的子字符串（也就是说必须统计 s 的所有子字符串中的唯一字符）。

核心思路：

• 该题没有思路，看了几篇题解才理解官方题解中所谓的计算每个字符对子字符串的贡献，解题方法中我先理解了动态规划，再慢慢理解了如何直接利用乘法直接计算字符的贡献。
• 动态规划的解法参考自下面参考内容中的链接。
  • dp[i][j] 代表以 s[i] 为结尾的所有子串中，字符 j 贡献的次数。【要计算以 s[i] 为结尾所有子串的所有字符贡献次数，只需要对 dp[i] 中 26 个元素求和即可】
  • 而比较以 s[i] 结尾的子串和以 s[i+1] 为结尾的子串，只有字符 s[i+1] 改变了贡献度，也就是说，dp[i] 与 dp[j] 比较，只有 dp[i][j+1] 与 dp[i][j] 不同。
  • 如此只需要更新字符 s[i+1] = c 的贡献度即可，假设字符 c 在 i+1 位置的前一个位置是 j，那么 c 在 i+1 位置的字符贡献度为 i+1-j，也就是两个索引的距离。
  • 以 LEETCODE 为例，最后一个 E 贡献的次数是 5，即子串 E、DE、ODE、CODE、TCODE 都只有一个 E ，再往前的子串中， E 就不是唯一字符了。
• 另一种解法是利用了乘法理论。【具体可看官方题解】
  • 有了动态规划的分析后，可以理解当前字符 c 对前面子串的贡献度是如何获得的，如此当前字符 c 对后面子串的贡献度是可以用同样的方法来获得的。
  • 因此对于 i 位置上的字符 c，假设其同一字符的前一个位置为 j，后一个位置为 k，则 c 对所有子串的独立贡献度为 (i-j)*(k-i)。【向前的贡献度为 i-j，向后的贡献度为 k-i】
  • 因此可以预处理字符串 s，将相同字符的下标放入数组中，方便计算。

代码实现：

• 动态规划解法代码实现如下：

  class Solution
  {
  public:
      int uniqueLetterString(string s)
      {
          int m = s.size(), cnt = 0, ans = 0;
          int MOD = 1e9+7;
          vector<int> dp(26); // 记录字符当前贡献的次数
          vector<int> idx(26, -1); // 前一个索引的位置
          for(int i = 0; i < m; ++i)
          {
              char c = s[i];
              c -= 'A';
              cnt = (cnt - dp[c] + (i - idx[c])) % MOD; // 当前所有字符的贡献，只有字符 c 的贡献改变
              dp[c] = i - idx[c]; // 当前贡献，留给下一次贡献更新
              idx[c] = i; // 更新位置
              ans = (ans + cnt) % MOD; // 记录最后结果
          }
          return ans;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21

• 官方题解中解法代码实现如下：

  class Solution {
  public:
      int uniqueLetterString(string s) {
          unordered_map<char, vector<int>> index;
          for (int i = 0; i < s.size(); i++) {
              index[s[i]].emplace_back(i);
          }
          int res = 0;
          for (auto &&[_, arr]: index) {
              arr.insert(arr.begin(), -1);
              arr.emplace_back(s.size());
              for (int i = 1; i < arr.size() - 1; i++) {
                  res += (arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i]);
              }
          }
          return res;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18

参考内容：

• 动态规划，递推每个字符贡献的次数即可

相关题目：

• 下面给出的题目中，方法未必一样，但问题形式较相似：
  • leetcode - 828.统计子串中的唯一字符
  • leetcode - 907.子数组的最小值之和
  • leetcode - 1498.满足条件的子序列数目
  • leetcode - 2104.子数组范围和
  • leetcode - 2262.字符串的总引力