🔗 🟡 2981. Find Longest Special Substring That Occurs Thrice I 1505

tags: `Weekly Contest 378` `暴力法(Brute Force)` `計數(Counter)`

這題是 2982 的數據範圍縮小版本，非暴力解法可以參考該題的解題紀錄，本篇文章中只會提到暴力解法。

題意

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

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

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

限制

$3 \leq s.length \leq 50$

思路：暴力枚舉 + 計數(Counter)

將每個字母每個特殊子字串的長度的出現次數記錄至 $cnt$ 中，暴力枚舉所有可能的子字串，並檢查是否為特殊子字串，若是特殊子字串則根據其長度累加出現次數至 $cnt$ 中，最後檢查是否有出現次數 $\geq 3$ 的特殊子字串即可。

複雜度分析

時間複雜度： $\mathcal{O}(n^3 + 26 \cdot n)$ $O (n^{3} + 26 \cdot n)$ = $\mathcal{O}(n^3)$ $O (n^{3})$
- 二重迴圈枚舉所有可能的子字串，再使用一個迴圈檢查是否為特殊子字串，故時間複雜度為 $\mathcal{O}(n^3)$
- 檢查是否有出現次數 $\geq 3$ 的特殊子字串的時間複雜度為 $\mathcal{O}(26 \cdot n)$
空間複雜度： $\mathcal{O}(26 \cdot n) = \mathcal{O}(n)$

class Solution:
    def maximumLength(self, s: str) -> int:
        n = len(s)
        cnt = [[0] * (n+1) for _ in range(26)]
        for i in range(n): # 枚舉 substring 的起點和終點
            for j in range(i, n):
                for k in range(i+1, j+1):
                    if s[k] != s[i]:
                        break
                else:
                    cnt[ord(s[i])-ord('a')][j-i+1] += 1
        ans = -1
        for i in range(26):
            for j in range(n, 0, -1):
                if cnt[i][j] >= 3:
                    ans = max(ans, j)
                    break
        return ans

class Solution {
public:
    int maximumLength(string s) {
        int n = s.size();
        vector<vector<int>> cnt(26, vector<int>(n+1, 0));
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                bool flag = true;
                for (int k = i+1; k <= j && flag; k++) {
                    if (s[k] != s[i]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) cnt[s[i]-'a'][j-i+1] += 1;
            }
        }
        int ans = -1;
        for (int i = 0; i < 26; i++) {
            for (int j = n; j > 0; j--) {
                if (cnt[i][j] >= 3) {
                    ans = max(ans, j);
                    break;
                }
            }
        }
        return ans;
    }
};