Maximum Length Substring With Two Occurrences

Difficulty: Easy | Acceptance: 65.50% | Paid: No Topics: Hash Table, String, Sliding Window

Given a string s, return the maximum length of a substring such that it contains at most two occurrences of each character.

• Examples
• Constraints
• Brute Force
• Sliding Window

Examples

Input: s = "bcbbbcba"
Output: 4
Explanation: The following substrings are valid:
- "bcbb" (Invalid, 'b' appears 3 times)
- "bcbc" (Valid, 'b' appears 2 times, 'c' appears 2 times)
- "cbcb" (Valid)
- "bcba" (Valid)
The longest valid substring is "bcbc" with a length of 4.

Input: s = "aaaa"
Output: 2
Explanation: The longest valid substring is "aa" where 'a' appears exactly 2 times. Any longer substring would have 'a' appearing more than 2 times.

Constraints

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

Brute Force

Intuition Since the constraint on the string length is small (up to 100), we can check every possible substring. For each starting index, we expand to the right, counting character frequencies until a character appears more than twice.

Steps

• Iterate through the string with a pointer i representing the start of the substring.
• Initialize a frequency map (or array) for the current substring.
• Iterate with a pointer j from i to the end of the string.
• Increment the count for s[j].
• If the count for s[j] exceeds 2, stop the inner loop (no need to check further extensions of this specific substring).
• Otherwise, update the maximum length found so far.
• Return the maximum length.

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        n = len(s)
        max_len = 0
        for i in range(n):
            count = {}
            for j in range(i, n):
                count[s[j]] = count.get(s[j], 0) + 1
                if count[s[j]] > 2:
                    break
                max_len = max(max_len, j - i + 1)
        return max_len

Complexity

• Time: O(n²) — We iterate through all possible substrings in the worst case.
• Space: O(1) — The frequency array/map has a fixed size of 26 (alphabet size).
• Notes: Simple to implement and efficient enough given the constraint n <= 100.

Sliding Window

Intuition We can optimize the solution to linear time using the sliding window technique. We maintain a window [left, right] that always satisfies the condition (at most two occurrences of each character). As we expand the window to the right, if a character count exceeds 2, we shrink the window from the left until the condition is restored.

Steps

• Initialize a frequency array of size 26 with zeros.
• Initialize left = 0 and max_len = 0.
• Iterate through the string with right from 0 to n-1.
• Increment the count of the character at s[right].
• While the count of s[right] is greater than 2:
  • Decrement the count of the character at s[left].
  • Increment left.
• Update max_len with the maximum of its current value and the window size (right - left + 1).
• Return max_len.

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        count = {}
        left = 0
        max_len = 0
        for right, char in enumerate(s):
            count[char] = count.get(char, 0) + 1
            while count[char] > 2:
                count[s[left]] -= 1
                left += 1
            max_len = max(max_len, right - left + 1)
        return max_len

Complexity

• Time: O(n) — Each character is processed at most twice (once by right and once by left).
• Space: O(1) — The frequency array has a fixed size of 26.
• Notes: This is the optimal approach for string problems involving substring constraints.