What is the main pattern used in Maximum Length Substring With Two Occurrences?

The problem primarily uses a sliding window with running state updates pattern, leveraging hash tables to track duplicate substrings efficiently.

Can substrings overlap in this problem?

Yes, overlapping substrings are valid and must be counted when determining maximum length occurrences.

What is the simplest approach given the constraints?

A brute-force check of all substrings works due to small string length, but a sliding window with hash tracking is much more efficient.

How does GhostInterview improve solving this problem?

It guides correct window management, hash collision handling, and ensures repeated substrings are detected without redundant checks.

What are common mistakes in implementing this pattern?

Common mistakes include failing to update hash state properly, missing overlapping substrings, and not handling rolling hash collisions.

#3090

Easy

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

每个字符最多出现两次的最长子字符串

给你一个字符串 s ，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的最大长度。示例 1：输入： s = "bcbbbcba" 输出： 4 解释：以下子字符串长度为 4，并且每个字符最多出现两次： "bcbb bcba " 。示例 2：输入： s = "aaaa" …

哈希表字符串滑动窗口

题目描述

给你一个字符串 s ，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的最大长度。

示例 1：

输入： s = "bcbbbcba"

输出： 4

解释：

以下子字符串长度为 4，并且每个字符最多出现两次："bcbbbcba"。

示例 2：

输入： s = "aaaa"

输出： 2

解释：

以下子字符串长度为 2，并且每个字符最多出现两次："aaaa"。

提示：

2 <= s.length <= 100
s 仅由小写英文字母组成。

lightbulb

解题思路

方法一：双指针

我们用两个指针 $i$ 和 $j$ 来维护一个滑动窗口，用一个数组 $cnt$ 来记录窗口中每个字符的出现次数。

每一次，我们将指针 $j$ 对应的字符 $c$ 加入窗口，然后判断 $cnt[c]$ 是否大于 $2$ ，如果大于 $2$ ，则将指针 $i$ 循环右移，直到 $cnt[c]$ 小于等于 $2$ 。此时，我们更新答案 $ans = \max(ans, j - i + 1)$ 。

最终，我们返回答案 $ans$ 。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(|\Sigma|)$ ，其中 $\Sigma$ 为字符集，本题中 $\Sigma = 26$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        cnt = Counter()
        ans = i = 0
        for j, c in enumerate(s):
            cnt[c] += 1
            while cnt[c] > 2:
                cnt[s[i]] -= 1
                i += 1
            ans = max(ans, j - i + 1)
        return ans

speed

复杂度分析

指标	值
时间	complexity can range from O(n^2) in brute-force substring checks to O(n log n) with binary search and hashing. Space complexity is O(n) to store substring hashes or rolling hash states. Efficient implementation balances speed and memory usage.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Are you checking for overlapping substrings carefully?
question_mark
Consider how sliding window updates affect your hash state.
question_mark
Think about edge cases with repeated characters and minimal length.

warning

常见陷阱

外企场景

error
Failing to update the window hash correctly after each shift.
error
Ignoring overlapping occurrences, which are valid for this problem.
error
Using brute-force without taking advantage of small constraints or hash optimizations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the maximum length substring appearing at least k times instead of twice.
arrow_right_alt
Return the substring itself rather than just the length.
arrow_right_alt
Limit substring length to a specific range and find the longest duplicate.

help

常见问题

外企场景

继续练习

#2982 找出出现至少三次的最长特殊子字符串 II #2981 找出出现至少三次的最长特殊子字符串 I #2953 统计完全子字符串