Leetcode 刷题记录（更新于2024-05-30）

毕设答辩终于结束，可以做点自己的事情了。

深感自己码力不足，决定重拾 leetcode 刷题，找回一点码力和算法能力。

---

2024-05-30：找出出现至少三次的最长特殊子字符串II

题面：找出出现至少三次的最长特殊子字符串II

记字符串长度为 $N$，第 $i$ 位为 $si (i=1,…,N)$，以 $s_i$ 为结尾的特殊字符串的最大长度为 $dp_i$。不难发现，如果 $s_i=s_{i-1}\,(i\neq 0)$，那么 $dp_i=dp_{i-1}+1$。我们需要找到出现至少 3 次的特殊字符串，故我们考虑记录以各字母结尾的最长的 3 个特殊字符串。小写英文字母一共 26 个，我们考虑维护 26 个长度固定为 3 的升序数组 $q_j\, (j=1,2,\dots,26)$，用以储存以字母表中第 iii 个字母结尾的最长的 3 个特殊字符串。

由定义，长度为 $l$ 的特殊字符串可以提供长度小于 $l$ 的字符串（各 1 个）。故 $\max_{j}q_{j,1}$ 即我们所寻找的答案。

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$

代码

void insert_vector3d(int x, vector<int>& v) {
    // v 从小到大排列，v.length = 3
    if (x < v[0]) return;
    if (x > v[2]) {
        v[0] = v[1];
        v[1] = v[2];
        v[2] = x;
        return;
    }
    if (x > v[1]) {
        v[0] = v[1];
        v[1] = x;
        return;
    }
    v[0] = x;
    return;
}

class Solution {
public:
    int maximumLength(string s) {
        int N = s.size();
        vector<int> dp(N);
        vector<vector<int>> letters(26);
        for (int i = 0; i < 26; i++) {
            letters[i] = vector({-1, -1, -1});
        }
        dp[0] = 1;
        letters[s[0] - 'a'][2] = 1;
        for (int i = 1; i < N; i++) {
            if (s[i] == s[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
            else {
                dp[i] = 1;
            }

            // letters[s[i] - 'a'].push_back(dp[i]);
            insert_vector3d(dp[i], letters[s[i] - 'a']);
        }

        int Max = -1; int tmp;
        for (int i = 0; i < 26; i++) {
            if (letters[i][0] != -1) {
                tmp = letters[i][0];
                Max = (tmp > Max)?tmp: Max;
            }
        }

        return Max;
    }
};

在力扣上也发表了题解。