LeetCode 3090 - Maximum Length Substring With Two Occurrences

LeetCode Problem 3090

Difficulty: 🟢 Easy
Topics: Hash Table, String, Sliding Window

Solution

Problem Understanding

The problem is asking for the maximum length of a substring in a given string s such that no character occurs more than twice within that substring. In other words, for any valid substring, each character can appear at most two times. You need to return the length of the longest such substring.

The input is a string s consisting only of lowercase English letters, with a length between 2 and 100. The output is a single integer representing the maximum length of a substring that satisfies the constraint on character occurrences.

Edge cases that are important to consider include strings where all characters are identical, strings where all characters are unique, and substrings that span the start or end of the input string. The constraints allow for a solution that is at worst quadratic, but a more efficient approach is possible with a sliding window.

Approaches

The brute-force approach would be to consider all possible substrings of s, check the count of each character in the substring, and only consider substrings where each character occurs at most twice. Then, return the maximum length among these valid substrings. While correct, this approach is too slow because generating all substrings is O(n²) and checking counts is O(n) per substring, resulting in an overall complexity of O(n³), which is not acceptable even for n ≤ 100.

The optimal approach uses a sliding window technique. The key observation is that we only need to track character counts within the current window. We expand the window by moving the right pointer and maintain counts of each character in a hash map or array. If any character count exceeds 2, we shrink the window from the left until all counts are at most 2. The length of the window at each step represents a valid substring, and the maximum length observed during this process is the answer.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(n)	Generate all substrings and validate counts
Sliding Window	O(n)	O(1)	Expand and shrink a window while maintaining counts, only 26 lowercase letters

Algorithm Walkthrough

1. Initialize a dictionary or array count to store counts of each character in the current window.

2. Initialize two pointers left and right to represent the current window boundaries, starting at 0.

3. Initialize a variable max_length to track the maximum length of a valid substring.

4. Iterate right over the string from 0 to n - 1:

5. Increment the count of s[right].

6. While any count exceeds 2, increment left and decrement the count of s[left] to shrink the window.

7. After ensuring all counts are at most 2, update max_length as the maximum of itself and right - left + 1.

8. Return max_length after processing the entire string.

Why it works: By maintaining a sliding window and dynamically enforcing the constraint on character occurrences, we ensure that every substring considered is valid. The window expansion guarantees that we explore all possible substrings efficiently without recomputation, and shrinking ensures the constraint is never violated.

Python Solution

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        count = [0] * 26  # there are 26 lowercase letters
        left = 0
        max_length = 0

        for right in range(len(s)):
            index = ord(s[right]) - ord('a')
            count[index] += 1

            while count[index] > 2:
                count[ord(s[left]) - ord('a')] -= 1
                left += 1

            max_length = max(max_length, right - left + 1)

        return max_length

In this implementation, we maintain an array count of size 26 to keep track of how many times each letter appears in the current window. The right pointer expands the window, and if the count of the current character exceeds 2, the left pointer moves forward, decrementing counts as necessary to maintain the constraint. max_length tracks the largest valid window encountered.

Go Solution

func maximumLengthSubstring(s string) int {
    count := [26]int{}
    left := 0
    maxLength := 0

    for right := 0; right < len(s); right++ {
        index := s[right] - 'a'
        count[index]++

        for count[index] > 2 {
            count[s[left]-'a']--
            left++
        }

        if right-left+1 > maxLength {
            maxLength = right - left + 1
        }
    }

    return maxLength
}

In Go, we use a fixed-size array of length 26 to track character counts instead of a dictionary for efficiency. The logic mirrors the Python version: expand the window, shrink if needed, and update maxLength accordingly. Integer arithmetic and array indexing are straightforward since we know all characters are lowercase English letters.

Worked Examples

Example 1: s = "bcbbbcba"

Step	Window	Counts	max_length
right=0	"b"	b=1	1
right=1	"bc"	b=1, c=1	2
right=2	"bcb"	b=2, c=1	3
right=3	"bcbb"	b=3, c=1 → shrink	"cbb" → b=2, c=1
right=4	"cbbb"	b=3, c=1 → shrink	"bbb" → b=2
right=5	"bbbc"	b=2, c=1	4
right=6	"bbcbc"	c=2, b=2	4
right=7	"bbcbc a"	a=1	4

Output: 4

Example 2: s = "aaaa"

Step	Window	Counts	max_length
right=0	"a"	a=1	1
right=1	"aa"	a=2	2
right=2	"aaa"	a=3 → shrink	"aa"
right=3	"aaa"	a=3 → shrink	"aa"

Output: 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed at most twice (once when right expands and once when left shrinks)
Space	O(1)	Only 26 characters are tracked in the count array

The time complexity is linear because the two pointers left and right each move at most n times. The space complexity is constant because the character set size is fixed at 26.

Test Cases

# Provided examples
assert Solution().maximumLengthSubstring("bcbbbcba") == 4  # mixed characters
assert Solution().maximumLengthSubstring("aaaa") == 2      # repeated single character

# Edge cases
assert Solution().maximumLengthSubstring("ab") == 2        # all unique
assert Solution().maximumLengthSubstring("aabbcc") == 6    # all characters appear twice
assert Solution().maximumLengthSubstring("abcabcabc") == 6 # repeated pattern

# Smallest input
assert Solution().maximumLengthSubstring("aa") == 2        # exactly two same characters

Test	Why
"bcbbbcba"	Mixed characters with some repeated over twice, tests sliding window logic
"aaaa"	Single character repeated, tests shrink logic
"ab"	All unique, simple case
"aabbcc"	All characters appear twice, maximum valid substring is the whole string
"abcabcabc"	Repeated pattern, verifies proper shrinking of window
"aa"	Minimum valid length, two same characters

Edge Cases

One important edge case is a string with all identical characters, such as "aaaaaa". This tests whether the algorithm correctly limits the count of each character to two and shrinks the window as necessary.

Another edge case is a string with all unique characters, such as "abcdef". Here, no shrinking is needed, and the maximum length should be the length of the entire string.

A third edge case is a pattern where multiple characters appear exactly twice within overlapping substrings, such as "aabbcc". The algorithm must handle multiple characters exceeding the allowed occurrence at different positions and adjust the window correctly to maintain the constraint for all characters.

In all these cases, the sliding window with a character count array ensures correctness by maintaining the invariant that each character occurs at most twice within the window.