3090. Maximum Length Substring With Two Occurrences

Problem Overview

You want the longest substring where every letter appears at most twice.

Intuition

You want the longest substring where every letter appears at most twice. As the right end grows, the window becomes invalid only when the newly added letter exceeds count 2. Shrink from the left until that letter is back to 2, then the whole window is valid again - track the maximum length.

Algorithm

1Maintain count[26] for the current window [l, r] and ans = 0.
2For each r: increment count[s[r]].
3While count[s[r]] > 2: decrement count[s[l]] and advance l.
4Update ans with r - l + 1.
5Return ans.

Example Walkthrough

Input: s = "bcbbbcba"

1.Indices: 0:b 1:c 2:b 3:b 4:b 5:c 6:b 7:a.
2.When the third b enters (index 3), shrink from the left until b appears at most twice.
3.A longest valid window is "bcba" (indices 4..7) with length 4.

Output: 4

Common Pitfalls

•At most two occurrences of each character, not at most two distinct characters.
•Only the count of the newly added letter can break the window - shrink until that letter is <= 2.
•Lowercase English only, so a size-26 array beats a hash map.
•Any substring of length at most 2 is always valid.

3090.cs

// Approach: Sliding window. Expand r; if any character appears more than twice
// in [l, r], advance l until every count is at most 2. Track the maximum
// valid window length.
// Complexity: O(n) time and O(1) space (26 letter counts).
public class Solution
{
    public int MaximumLengthSubstring(string s)
    {
        int ans = 0;
        int[] count = new int[26];

        for (int l = 0, r = 0; r < s.Length; ++r)
        {
            ++count[s[r] - 'a'];
            while (count[s[r] - 'a'] > 2)
                --count[s[l++] - 'a'];
            ans = Math.Max(ans, r - l + 1);
        }

        return ans;
    }
}

Was this solution helpful?