🔗 🟡 2982. Find Longest Special Substring That Occurs Thrice II 1773

tags: `Weekly Contest 378` `分組循環` `分類討論` `排序(Sorting)` `堆積(Heap)` `計數(Counter)` `雜湊表(Hash Table)`

這題是 2981 的數據範圍加大版本，暴力解法可以參考該題的解題紀錄，但在本題中使用會 TLE 。

題意

給定一個全由小寫字母組成的字串 $s$ 。

如果一個字串只包含單一字元，則稱之為 特殊的(Special)* 。例如 $"abc"$ 不是特殊字串，但 $"ddd"$ 、 $"zz"$ 和 $"f"$ 都是特殊字串。

請返回 $s$ 中出現至少三次的最長特殊子字串的長度，如果沒有這樣的特殊子字串，則返回 $-1$ 。

限制

$3 \leq s.length \leq 5 \times 10^5$

思路：分組循環 + 分類討論

題意中的特殊字串，即為連續的相同字元。因此可以用分組循環的思路找出每一段連續的相同字元

方法一：分組循環 + 暴力枚舉 + 計數(Counter)

在取得每一段的長度後，最直接的做法是計算其對不同長度的貢獻。例如一個長度為 $k$ 的子串，則其對於長度為 $k$ 的特殊子字串的貢獻為 $k$ ，對於長度為 $k-1$ 的特殊子字串的貢獻為 $k-1$ ，以此類推。因此對於每一個字母，可以用一個長度為 $n+1$ 的陣列來記錄每個長度的出現次數，最後再找出出現次數 $\geq 3$ 的最大長度即可。

需要注意的是，在 Python 中若使用 Counter 來記錄每一個字元的連續長度的貢獻，會導致 TLE，因此需要改用二維陣列來記錄，而最長的特殊子字串長度為
$n$ ，因此值域為 $[0, n]$ 。

此外，還能夠有一些優化：

由於長度為 $n$ 的子字串最多只會出現 $1$ 次，長度為 $n-1$ 的子字串最多只會出現 $2$ 次，因此在檢查答案時，可以從 $n-2$ 開始檢查，並且只要找到一個符合條件的即可跳出迴圈。
在計算貢獻時也不用考慮全部的長度，由於長度為 $k-2$ 的特殊子字串的貢獻為 $3$ ，只需要考慮長度為 $k$ 、 $k-1$ 、 $k-2$ 的特殊子字串的貢獻即可。

複雜度分析

時間複雜度： $\mathcal{O}(n + 26n) = \mathcal{O}(n)$ $O (n + 26 n) = O (n)$
- 雖然分組循環中有雙重迴圈，但 $i$ 只會增加 $n$ 次；在計算貢獻時，也只會各遍歷一次不重疊的每一段，而每段的總長度也為 $n$ ，故分組循環的時間複雜度為 $\mathcal{O}(n)$
空間複雜度： $\mathcal{O}(26n) = \mathcal{O}(n)$

class Solution:
    def maximumLength(self, s: str) -> int:
        n = len(s)
        # groups = [Counter() for _ in range(26)] # TLE
        groups = [[0] * (n+1) for _ in range(26)] # AC
        i = 0
        while i < n: # 分組循環
            st, i, idx = i, i+1, ord(s[i]) - ord("a")
            while (i < n and s[i] == s[st]):
                i += 1
            # for k in range(1, i - st + 1): # 長度為 k 的子字串有 i - st - k + 1 個
            for k in range(i - st, max(0, i - st - 3), -1): # 其實最多考慮 3 個就夠了
                groups[idx][k] += i - st - k + 1
        ans = -1
        for g in groups:
            # for i in range(n, 0, -1): 
            for i in range(n-2, 0, -1): # 需要出現至少 3 次
                if g[i] >= 3: # 滿足條件
                    ans = max(ans, i)
                    break
        return ans

class Solution {
public:
    int maximumLength(string s) {
        int n = s.size(), i = 0;
        vector<vector<int>> groups(26, vector<int>(n+1, 0));
        while (i < n){ // 分組循環
            int st = i++;
            while (i < n && s[i] == s[st]) i++;
            // for (int k = 1; k <= i - st; k++) // 長度為 k 的子字串有 i - st - k + 1 個
            for (int k = i - st; k >= max(1, i - st - 2); k--) // 其實最多考慮 3 個就夠了
                groups[s[st] - 'a'][k] += (i - st) - k + 1; 
        }
        int ans = -1;
        for (auto g : groups)
            // for (int i = n; i > 0; i--)
            for (int i = n-2; i > 0; i--) // 需要出現至少 3 次
                if (g[i] >= 3){ // 滿足條件
                    ans = max(ans, i);
                    break;
                }
        return ans;
    }
};

方法二：分組循環 + 分類討論 + 排序(Sorting)

如同方法一中的思路，但由於我們只需要考慮出現 $3$ 次以上的情況，因此對於長度為 $k$ 的子字串，其實只需要考慮其對於長度為 $k$ 、 $k-1$ 、 $k-2$ 的特殊子字串的貢獻即可。此外，將每一段的長度由大到小排序後，會發現答案至少為第 $3$ 大的長度，因此只需要考慮前 $3$ 大的長度即可。

同樣是使用分組循環中，將每段的長度加入到該字母的分組 $g_i$ 中，最後對於每一個字母，找出前 $3$ 大的長度，再分類討論即可。若 $g_i$ 為空，則跳過，否則則將 $g_i$ 由大到小排序，並假設長度 $m \geq 3$ ，方便以下說明：

由於 $g_i[0]$ 可以產生 $3$ 個長度為 $g_i[0]-2$ 的特殊子字串，因此可以更新答案為 $max(ans, g_i[0]-2)$
由於 $g_i[0]$ 可以產生 $2$ 個長度為 $g_i[0]-1$ 的特殊子字串，再加上一個長度為 $g_i[1]$ 的特殊子字串，故至少有 $3$ 個長度為 $min(g_i[0]-1, g_i[1])$ 的特殊子字串，因此可以更新答案為 $max(ans, min(g_i[0]-1, g_i[1]))$
由於 $g_i[0] \geq g_i[1] \geq g_i[2]$ ，故至少能產生 $3$ 個長度為 $g_i[2]$ 的特殊子字串，因此可以更新答案為 $max(ans, g_i[2])$

初始化答案為 $0$ ，若答案為 $0$ 則回傳 $-1$ 。可以透過檢查 $m$ 來判斷是否要執行上述的更新操作、或是直接在 $g_i$ 後加上 $2$ 個 $0$ ，可以不用考慮 $m < 3$ 的情況，在後續的更新操作中也不會影響答案。

複雜度分析

時間複雜度： $\mathcal{O}(n + 26 \cdot n \log n) = \mathcal{O}(n \log n)$ $O (n + 26 \cdot n lo g n) = O (n lo g n)$
- 分組循環的時間複雜度為 $\mathcal{O}(n)$
- 分類討論的時間複雜度為 $\mathcal{O}(26 \cdot n \log n) = \mathcal{O}(n \log n)$
空間複雜度： $\mathcal{O}(n)$ ，最壞情況下會有 $n$ 個長度為 $1$ 的子字串

class Solution:
    def maximumLength(self, s: str) -> int:
        n = len(s)
        groups = [[] for _ in range(26)]
        i = 0
        while i < n: # 分組循環
            st, i = i, i+1
            while (i < n and s[i] == s[st]):
                i += 1
            groups[ord(s[st]) - ord("a")].append(i - st)
        ans = 0
        for g in groups:
            m = len(g)
            if m == 0: continue
            g.sort(reverse=True)
            ans = max(ans, g[0]-2)
            if m > 1: ans = max(ans, min(g[0]-1, g[1]))
            if m > 2: ans = max(ans, g[2])
        return ans if ans > 0 else -1

class Solution {
public:
    int maximumLength(string s) {
        int n = s.size(), i = 0;
        vector<vector<int>> groups(26, vector<int>());
        while (i < n){
            int st = i++;
            while (i < n && s[i] == s[st]) i++;
            groups[s[st] - 'a'].push_back(i - st);
        }
        int ans = 0;
        for (auto g : groups){
            int m = g.size();
            if (m == 0) continue;
            sort(g.begin(), g.end(), greater<int>());
            ans = max(ans, g[0] - 2);
            if (m > 1) ans = max(ans, min(g[0] - 1, g[1]));
            if (m > 2) ans = max(ans, g[2]);
        }
        return ans > 0 ? ans : -1;
    }
};

方法三：分組循環 + 分類討論 + 堆積(Heap)

如同方法二的思路，但既然我們只需要考慮前 $3$ 大的值，那不妨使用堆積(Heap) 來維護每組的前 $3$ 大的值。在每一段的長度加入到該字母的分組 $g_i$ 中後，若長度超過 $3$ 個，則將最小的長度移除。在 Python 中可以使用 heapq 模組中的 heappush 和 heappop 來維護 Min Heap，而在 C++ 中可以使用 priority_queue 來維護 Min Heap。

新建一個長度為 $3$ 的陣列 $tmp$ 來存放 $g_i$ 的前 $3$ 大的值，並從將堆頂的元素依次放到 $tmp[m-1], tmp[m-2], tmp[m-3]$ 中，其中 $m$ 為 $g_i$ 的長度，這種寫法可以考慮到 $m < 3$ 的情況，讀者可以自行驗證。如此 $tmp$ 中的元素即為 $g_i$ 的前 $3$ 大的值，最後如同方法二中的分類討論思路，根據 $tmp$ 的值來更新答案。

複雜度分析

時間複雜度： $\mathcal{O}(n \log 3 + 26 \cdot 3 \log 3) = \mathcal{O}(n)$ $O (n lo g 3 + 26 \cdot 3 lo g 3) = O (n)$
- 分組循環的時間複雜度為 $\mathcal{O}(n + n \log 3) = \mathcal{O}(n)$ ，因為 heappush 和 heappop 的時間複雜度為 $\mathcal{O}(\log 3)$ ，且最多只會執行 $O(n)$ 次
- 分類討論的時間複雜度為 $\mathcal{O}(26 \cdot 3 \log 3) = \mathcal{O}(1)$ 。
空間複雜度： $\mathcal{O}(26 \cdot 3) = \mathcal{O}(1)$

class Solution:
    def maximumLength(self, s: str) -> int:
        n = len(s)
        groups = [[] for _ in range(26)]
        i = 0
        while i < n: # 分組循環
            st = i
            while (i < n and s[i] == s[st]):
                i += 1
            idx = ord(s[st]) - ord("a")
            if len(groups[idx]) >= 3:
                heappushpop(groups[idx], (i - st)) # Min heap
            else:
                heappush(groups[idx], (i - st)) # Min heap
        ans = 0
        for g in groups:
            m = len(g)
            if m == 0: continue
            tmp = [0] * 3
            for i in range(m-1, -1, -1):
                tmp[i] = heappop(g)
            ans = max(ans, tmp[0]-2, min(tmp[0]-1, tmp[1]), tmp[2])
        return ans if ans > 0 else -1

class Solution {
public:
    int maximumLength(string s) {
        int n = s.size(), i = 0;
        priority_queue<int, vector<int>, greater<int>> groups[26]; // Min heap
        while (i < n){
            int st = i++;
            while (i < n && s[i] == s[st]) i++;
            groups[s[st] - 'a'].push(i - st);
            if (groups[s[st] - 'a'].size() > 3) groups[s[st] - 'a'].pop();
        }
        int ans = 0;
        for (auto g : groups){
            int m = g.size();
            if (m == 0) continue;
            vector<int> tmp(3, 0);
            for (int i = m-1; i >= 0; i--) tmp[i] = g.top(), g.pop();
            ans = max({ans, tmp[0] - 2, min(tmp[0] - 1, tmp[1]), tmp[2]});
        }
        return ans > 0 ? ans : -1;
    }
};