#3090

Easy

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Maximum Length Substring With Two Occurrences

Find the maximum length substring where some substring occurs at least twice using a sliding window and hash mapping strategy.

hash table string sliding window

Problem Statement

Given a string s, determine the maximum length of any substring that appears at least twice in s. The substring occurrences may overlap but must share identical characters. Return the length of this substring.

For example, if s = "bcbbbcba", the longest substring appearing twice is "bbbb" with length 4. Constraints are small enough to allow iterative checks, but an efficient sliding window with a hash table provides faster verification of repeated substrings.

Examples

Example 1

Input: s = "bcbbbcba"

Output: 4

Example 2

Input: s = "aaaa"

Output: 2

Constraints

2 <= s.length <= 100
s consists only of lowercase English letters.

Solution Approach

Use Sliding Window With Hash Tracking

Iterate through the string using a window of increasing length. Store each substring in a hash set and check if it has been seen before. If a duplicate is found, update the maximum length. This directly applies the sliding window with running state updates pattern.

Binary Search on Length

Optionally, perform binary search on possible substring lengths to minimize checks. For each length, use the hash set approach to verify duplicates. This reduces unnecessary comparisons and demonstrates efficient substring checking beyond naive iteration.

Handle Collisions Carefully

When using hash-based tracking, ensure that different substrings do not collide. Using rolling hash techniques or combining string slices with unique identifiers prevents false positives. This is critical for correctness in the sliding window pattern with state updates.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Two Pointers

We use two pointers $i$ and $j$ to maintain a sliding window, and an array $cnt$ to record the occurrence times of each character in the window.

1

2

3

4

5

6

7

8

9

10

11

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

Continue Practicing

#2982 find longest special substring that occurs thrice ii #2981 find longest special substring that occurs thrice i #2953 count complete substrings