DSA problem

Longest Substring with At Most Two Distinct Characters

MediumSliding Window - Dynamic SizePattern: Variable-Size Sliding Windowtop600GoogleAmazonFacebookBloomberg

Given a string s, return the length of the longest substring that contains at most two distinct characters.

This is a classic constraint-bounded substring problem. A brute-force scan of all substrings would take quadratic time, but the at-most-two-distinct condition has a useful property: if a substring is valid, you can always check validity incrementally as you grow or shrink its boundaries.

The variable-size sliding window handles this elegantly. Use a hash map to count the characters currently inside the window. Advance the right pointer to extend the window, adding the new character to the map. Whenever the map holds more than two distinct characters, advance the left pointer, decrementing counts and removing any character whose count reaches zero, until only two distinct characters remain. The longest window observed during this scan is the answer.

Examples

Example 1

Input: s = "eceba"

Output: 3

Explanation: The substring "ece" has length 3 and contains only two distinct characters, e and c. No longer substring satisfies the constraint.

Example 2

Input: s = "ccaabbb"

Output: 5

Explanation: The substring "aabbb" has length 5 and contains the two distinct characters a and b. It is the longest valid substring.

Example 3

Input: s = "abaccc"

Output: 4

Explanation: The substring "accc" has length 4 with the two distinct characters a and c. The substring "abac" also has length 4, but no valid substring is longer.

Constraints

1 <= s.length <= 10^5
s consists of English letters.

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

sliding-windowhash-mapstringtwo-pointers

Browse all DSA problems