196. Longest Substring With At Most Two Distinct Characters

Longest Substring With At Most Two Distinct Characters

You are given a string s.

Return the length of the longest substring of s that contains at most two distinct characters.

A substring is a contiguous sequence of characters inside a string. For example, in the string "abac", some substrings are "a", "ab", "aba", and "abac".

A valid substring may contain only one distinct character, such as "aaaa", or exactly two distinct characters, such as "abbba".

Your task is to find the maximum length among all valid substrings.

Class Definition

Implement the class LongestSubstringWithAtMostTwoDistinctCharacters.

Method Signature

int lengthOfLongestSubstringTwoDistinct(String s)

s is the input string.
Returns the length of the longest contiguous substring that contains at most two distinct characters.

Input Format

The method receives one parameter:

String s: the string to analyze.

Output Format

The method returns an integer representing the maximum length of any substring containing at most two distinct characters.

Constraints

0 ≤ s.length() ≤ 100,000
s may contain lowercase letters, uppercase letters, digits, spaces, and special characters.
The substring must be contiguous.
The substring must contain at most two distinct characters.
An empty string has answer 0.

Expected Approach

Use a sliding window with two pointers.

Maintain the frequency of each character inside the current window. Expand the right side of the window one character at a time. If the window contains more than two distinct characters, move the left pointer forward and decrease character counts until the window becomes valid again.

During this process, keep track of the largest valid window length seen so far.

Examples

Example 1

Method call:
lengthOfLongestSubstringTwoDistinct(s = "abaccc")

Output:
4

Explanation:
The longest valid substring is "accc", which contains only the characters 'a' and 'c'.

Example 2

Method call:
lengthOfLongestSubstringTwoDistinct(s = "zzxyyyxx")

Output:
6

Explanation:
The longest valid substring is "xyyyxx", which contains only the characters 'x' and 'y'.

Example 3

Method call:
lengthOfLongestSubstringTwoDistinct(s = "pqqqprrr")

Output:
5

Explanation:
The longest valid substring is "pqqqp", which contains only the characters 'p' and 'q'.

Example 4

Method call:
lengthOfLongestSubstringTwoDistinct(s = "111223333")

Output:
6

Explanation:
The longest valid substring is "223333", which contains only the characters '2' and '3'.

Example 5

Method call:
lengthOfLongestSubstringTwoDistinct(s = "k")

Output:
1

Explanation:
The entire string is valid because it contains only one distinct character.