Longest Substring with At Most Two Distinct Characters Python/Java solution

Implement a sliding window with a dictionary in Python or a HashMap in Java. Expand the right pointer to include characters and update counts, then shrink the left pointer when more than two distinct characters appear. Track the maximum window length during the traversal.

What is the best approach for Longest Substring with At Most Two Distinct Characters?

The best approach uses a sliding window with a hash table to track character frequencies. Two pointers expand and shrink the window while maintaining at most two distinct characters. Each character is processed once, giving O(n) time complexity and O(1) space.

Is Longest Substring with At Most Two Distinct Characters asked at Google/Amazon/Meta?

Substring problems using sliding window patterns frequently appear in interviews at companies like Google, Amazon, and Meta. Variations include 'at most K distinct characters' or 'longest substring without repeating characters'. Recognizing the sliding window template is key for these interviews.

What data structure is used in Longest Substring with At Most Two Distinct Characters?

A hash table (or dictionary/map) stores the frequency of characters inside the current sliding window. Combined with two pointers, this structure allows constant‑time updates and quick checks on how many distinct characters exist in the window.

What is the time complexity of Longest Substring with At Most Two Distinct Characters?

The optimal sliding window solution runs in O(n) time because each character enters and leaves the window at most once. Space complexity is O(1) since the hash map stores at most three characters while enforcing the two‑distinct constraint.

Description Solution Video 10:45

159. Longest Substring with At Most Two Distinct Characters

Q: Is Longest Substring with At Most Two Distinct Characters easy or hard?

The problem is rated Medium because it requires recognizing the sliding window pattern and maintaining a dynamic constraint on distinct characters. Once you know the 'at most K distinct characters' template, the implementation becomes straightforward.

Q: How to solve Longest Substring with At Most Two Distinct Characters in O(n)?

Use a sliding window with two pointers. Move the right pointer across the string while updating a frequency map of characters in the window. When the number of distinct characters exceeds two, move the left pointer forward and decrease counts until the window becomes valid again.

Medium57.0% acceptance5 companiesPremium elsewhere, free here

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

Example 1:

Input: s = "eceba"
Output: 3
Explanation: The substring is "ece" which its length is 3.

Example 2:

Input: s = "ccaabbb"
Output: 5
Explanation: The substring is "aabbb" which its length is 5.

Constraints:

1 <= s.length <= 10⁵
s consists of English letters.

Asked at 5 companies

Tiktok

Google Meta Amazon Microsoft

Topics

10:45

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

159. Longest Substring with At Most Two Distinct Characters

Asked at 5 companies

Topics

Similar problems