3090. Maximum Length Substring With Two Occurrences

Hash Table
String
Sliding Window

TIME

O(n)

SPACE

O(26)

Intuition

"At most two occurrences of each character" is preserved when a window shrinks, so a two-pointer sliding window applies: extend the right edge greedily, and whenever the constraint breaks, pull the left edge in until it holds again.

Only the character just added can push a count above 2, so the shrink loop only needs to watch that one.

Approach

Keep a count array of size 26 and a left pointer.
For each right index r:
- Increment the count of s[r].
- While that count exceeds 2, decrement the count of s[left] and advance left.
- Update the answer with r - left + 1.
Return the largest window seen.

Complexity

Time: O(n), left only moves forward, so the work is amortized linear
Space: O(26) = O(1)

Edge Cases

All identical characters (Example 2) → answer is exactly 2
All distinct characters → the whole string qualifies → answer n
Length is at least 2 per constraints, so the answer is at least 2
This is the k = 2 case of the general "at most k frequency" window (see problem 2958)

Code

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        """
        3090. Maximum Length Substring With Two Occurrences
        Time: O(n)
        Space: O(26)
        """
        count = [0] * 26
        left = 0
        best = 0

        for r, ch in enumerate(s):
            c = ord(ch) - 97
            count[c] += 1
            # only the just-added character can exceed the limit
            while count[c] > 2:
                count[ord(s[left]) - 97] -= 1
                left += 1
            best = max(best, r - left + 1)

        return best

/**
 * 3090. Maximum Length Substring With Two Occurrences
 * Time: O(n)
 * Space: O(26)
 */
class Solution {
    public int maximumLengthSubstring(String s) {
        int[] count = new int[26];
        int left = 0, best = 0;

        for (int r = 0; r < s.length(); r++) {
            int c = s.charAt(r) - 'a';
            count[c]++;
            // only the just-added character can exceed the limit
            while (count[c] > 2) {
                count[s.charAt(left) - 'a']--;
                left++;
            }
            best = Math.max(best, r - left + 1);
        }

        return best;
    }
}