LeetCode 解題筆記：3090. Maximum Length Substring With Two Occurrences

作者：王一哲
日期：2026年8月14日


LeetCode 題目連結：3090. Maximum Length Substring With Two Occurrences

解題想法

簡單題。題目給一個字串 $s$，要找出每個字母最多只會出現兩次的最長子字串長度，基本上就是 2958. Length of Longest Subarray With at Most K Frequency 的簡化版。這題很適合用滑動視窗 (sliding window) 解題。

1. $s$ 的長度為 $n$，視窗左端點 $left$ 起始值為 $0$，答案 $ans$ 預設為 $0$，用表格或字典 $cnt$ 記錄視窗範圍內的數字數量。
2. 用一層 for 迴圈跑視窗右端點 $right = 0$ 到 $right = n-1$，$cnt[s[right]] += 1$。
3. 再用一層 while 迴圈，如果 $left < right$ 且 $cnt[s[right]] > 2$ 繼續執行，移除左端點的字母 $cnt[s[left]] -= 1$，左端點向右移 1 格 $left += 1$。
4. 跑完 while 迴圈時，$s[right]$ 到 $s[left]$ 之間的字母數量都小於等於 $2$，視窗長度為 $right - left + 1$，這可能是新的答案，更新 $ans$。

Python 程式碼

使用預設的字典計數。Runtime: 2 ms, beats 81.56%. Memory: 19.1 MB, beats 98.37%.

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        cnt = dict()
        n, ans, left = len(s), 0, 0
        for right in range(n):
            if s[right] not in cnt:
                cnt[s[right]] = 1
            else:
                cnt[s[right]] += 1
            while left < right and cnt[s[right]] > 2:
                cnt[s[left]] -= 1
                left += 1
            ans = max(ans, right - left + 1)
        return ans

使用 defaultdict 計數。Runtime: 3 ms, beats 76.16%. Memory: 19.2 MB, beats 60.10%.

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        cnt = defaultdict(int)
        n, ans, left = len(s), 0, 0
        for right in range(n):
            cnt[s[right]] += 1
            while left < right and cnt[s[right]] > 2:
                cnt[s[left]] -= 1
                left += 1
            ans = max(ans, right - left + 1)
        return ans

使用表格計數。Runtime: 3 ms, beats 76.16%. Memory: 19.0 MB, beats 98.37%.

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        cnt = [0] * 26
        n, ans, left = len(s), 0, 0
        for right in range(n):
            cnt[ord(s[right]) - ord('a')] += 1
            while left < right and cnt[ord(s[right]) - ord('a')] > 2:
                cnt[ord(s[left]) - ord('a')] -= 1
                left += 1
            ans = max(ans, right - left + 1)
        return ans

C++ 程式碼

使用 map 計數。Runtime: 4 ms, beats 28.78%. Memory: 9.7 MB, beats 44.69%.

class Solution {
public:
    int maximumLengthSubstring(string s) {
        map<char, int> cnt;
        int n = (int)s.size(), ans = 0, left = 0;
        for(int right = 0; right < n; right++) {
            cnt[s[right]]++;
            while(left < right && cnt[s[right]] > 2) {
                cnt[s[left]]--;
                left++;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

使用 unordered_map 計數。Runtime: 3 ms, beats 42.93%. Memory: 9.5 MB, beats 57.72%.

class Solution {
public:
    int maximumLengthSubstring(string s) {
        unordered_map<char, int> cnt;
        int n = (int)s.size(), ans = 0, left = 0;
        for(int right = 0; right < n; right++) {
            cnt[s[right]]++;
            while(left < right && cnt[s[right]] > 2) {
                cnt[s[left]]--;
                left++;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

表格計數。Runtime: 0 ms, beats 100.00%. Memory: 9.3 MB, beats 70.10%.

class Solution {
public:
    int maximumLengthSubstring(string s) {
        int cnt[26] = {0};
        int n = (int)s.size(), ans = 0, left = 0;
        for(int right = 0; right < n; right++) {
            cnt[s[right] - 'a']++;
            while(left < right && cnt[s[right] - 'a'] > 2) {
                cnt[s[left] - 'a']--;
                left++;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

C 語言程式碼

表格計數。Runtime: 0 ms, beats 100.00%. Memory: 8.9 MB, beats 100.00%.

int maximumLengthSubstring(char* s) {
    int cnt[26] = {0};
    int n = strlen(s), ans = 0, left = 0;
    for(int right = 0; right < n; right++) {
        cnt[s[right] - 'a']++;
        while(left < right && cnt[s[right] - 'a'] > 2) {
            cnt[s[left] - 'a']--;
            left++;
        }
        if (right - left + 1 > ans) {
            ans = right - left + 1;
        }
    }
    return ans;
}