題目網址：https://leetcode.cn/problems/count-unique-characters-of-all-substrings-of-a-given-string/

題意：定義一函數 countUniqueChars(s) 返回 string s 中只出現一次的 char 之個數。

e.g. s = "LEETCODE", 其中 L、T、C、O、D 皆只出現過一次, 因此 countUniqueChars(s) = 5。

今給一 string s, 返回 countUniqueChars(t) 的總和, 其中 t 是 s 的 substring。

注意：

  • 有些 substring 是會重複的, 計算時也必須算上這些重複的 substring（也就是說, 統計 s 所有 substring 中只出現一次的 char）。
  • s 僅由大寫英文所組成。

Solution 1：

想法：與其計算所有 substring 中的 unique char 個數, 不如計算單一 char 在哪些 substring 是 unique char, 最後做加總即為所求

  • 考慮 s = XAXAXXAX 並專注於使第二個 A 成為 unique char
  • 我們可以取 XA(XAXX)AX, 其中 () 中間的範圍就是符合條件的 substring 範圍
  • 因此, 能使第二個 A 為 unique char 的總共有 6 種 substring
    • 第二個 A 以左（不含 A）可取 ""、X 這 2 種 substring
    • 第二個 A 以右（不含 A）可取 ""、X、XX 這 3 種 substring
    • 總共有 A、AX、AXX 和 XA、XAX、XAXX 這 6 種 substring
  • 若想求 idx = i 的 char 為 unique char 的 substring 個數, 我們需要：
    • 前一個跟 s[i] 相同的 char 的 idx j
    • 後一個跟 s[i] 相同的 char 的 idx k
    • substring 個數 = (i - j) * (k - i)
  • 因此, 我們要紀錄相同的 char 所有出現的位置
  • 特殊情況：當 s 中和 s[i] 相同的 char 不滿 2 個時, 也就是 s[i] 找不到前一個相同的 char 或後一個相同的 char 時
  • 解決辦法：在每個 char 紀錄所有位置的開頭加上 1, 且結尾加上 n, 這樣即便 s 中沒有任何跟 s[i] 相同的 char 也能計算 substring 個數 = (i + 1) * (n - i)
    • e.g. s = XA, 可得到 A 的 idx = [-1, 1, 2]
      • A 以左（不含 A）可取 ""、X 這 2 種 substring
      • A 以右（不含 A）可取 "" 這 1 種 substring
      • (1 + 1) * (2 - 1) = 2, 總共有 A、XA 這 2 種 substring
class Solution {
public:
    int uniqueLetterString(string s) {
        const int n = s.size();
        vector<vector<int>> idx(26);

        // 所有位置開頭之前加上 -1
        for (int i = 0; i < 26; ++i) {
            idx[i].emplace_back(-1);
        }

        // 紀錄所有 s[i] 出現的位置
        for (int i = 0; i < n; ++i) {
            idx[s[i] - 'A'].emplace_back(i);
        }

        // 所有位置結尾之後加上 n
        for (int i = 0; i < n; ++i) {
            idx[s[i] - 'A'].emplace_back(n);
        }

        int res = 0;
        for (int i = 0; i < 26; ++i) {
            for (int j = 1; j < idx[i].size() - 1; ++j) {
                res += (idx[i][j] - idx[i][j - 1]) * (idx[i][j + 1] - idx[i][j]);
            }
        }

        return res;
    }
};
  • time：$O(n)$ ➔ 遍歷 s
  • space：$O(n)$ ➔ idx 紀錄 s 中每個元素出現的位置

Solution 2：

想法：利用 Sliding window, 概念同 Solution 1, 只是計算 idx = i 之 substring 個數時, 只會用到前一個和後一個相同 char 的 idx, 故不需要一次紀錄所有相同 char 的位置

  • 首先, 我們先將 last2idx 每個 char 的前兩個位置初始化為 1, -1（當前 i 作為第三個位置）
    ➔ 貢獻值公式：(第二個位置 - 第一個位置) * (i - 第二個位置)
  • 遍歷 s 中每個 char, 此時計算前一個 char（第二個位置）的貢獻值, 並累加到 res 中
  • 假如當前 char 是首次出現, 因為前兩個 char 的出現位置都是 1, 相減後為 0, 所以累加值還是 0
  • 然後更新 last2idx 中的值
  • 由於每次都是計算該 char 的前一個位置之貢獻值, 所以最後還需要一個 for loop 去計算每個 char 最後出現位置的貢獻值。由於最後一個 char 後面沒有相同 char 了, 故用 n 來替代其後一個 idx
class Solution {
public:
    int uniqueLetterString(string s) {
        const int n = s.size();
        int res = 0;

        // 紀錄前兩次相同 char 出現的位置
        vector<vector<int>> last2idx(26, vector<int>(2, -1));

        // 前兩次的出現位置，加上當前位置 i，可得知前一個位置的貢獻值
        for (int i = 0; i < n; ++i) {
            const int ch = s[i] - 'A';
            res += (last2idx[ch][1] - last2idx[ch][0]) * (i - last2idx[ch][1]);
            last2idx[ch][0] = last2idx[ch][1];
            last2idx[ch][1] = i;
        }

        // 計算每個 char 最後出現位置的貢獻值
        for (int ch = 0; ch < 26; ++ch) {
            res += (last2idx[ch][1] - last2idx[ch][0]) * (n - last2idx[ch][1]);
        }

        return res;
    }
};
  • time：$O(n)$ ➔ 遍歷 s
  • space：$O(1)$ ➔ $O(26 \cdot 2)$, 因為 last2idx 只需常數空間