197. Longest Substring With At Most N Distinct Characters

Longest Substring With At Most N Distinct Characters

You are given a string s and an integer n.

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

A substring is a contiguous sequence of characters inside a string. For example, in the string "cabd", some substrings are "c", "ca", "cab", and "cabd".

A valid substring may contain fewer than n distinct characters or exactly n distinct characters, but it must not contain more than n distinct characters.

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

Class Definition

Implement the class LongestSubstringWithAtMostNDistinctCharacters.

Method Signature

int lengthOfLongestSubstringNDistinct(String s, int n)

Returns the length of the longest contiguous substring of s that contains at most n distinct characters.
If no non-empty substring can be valid, return 0.

Input Format

The method receives:

String s: the input string.
int n: the maximum number of distinct characters allowed in a valid substring.

Output Format

The method returns an integer representing the maximum possible length of a substring containing at most n distinct characters.

Constraints

0 ≤ s.length() ≤ 100,000
0 ≤ n ≤ 100,000
s contains only printable ASCII characters.
The input string s will never be null.
The method must not receive null as a parameter value.

Examples

Example 1

Method Call:
lengthOfLongestSubstringNDistinct(s = "ecebaaa", n = 2)

Output:
4

Explanation:
The longest valid substring is "baaa", which contains only two distinct characters: 'b' and 'a'. Its length is 4.

Example 2

Method Call:
lengthOfLongestSubstringNDistinct(s = "aaabbbccc", n = 2)

Output:
6

Explanation:
The substring "aaabbb" contains only two distinct characters and has length 6. The substring "bbbccc" is also valid with length 6.

Example 3

Method Call:
lengthOfLongestSubstringNDistinct(s = "pqpqs", n = 2)

Output:
4

Explanation:
The longest valid substring is "pqpq", which contains only two distinct characters: 'p' and 'q'. Its length is 4.

Example 4

Method Call:
lengthOfLongestSubstringNDistinct(s = "xyz", n = 0)

Output:
0

Explanation:
No non-empty substring can contain at most 0 distinct characters, so the answer is 0.

Example 5

Method Call:
lengthOfLongestSubstringNDistinct(s = "", n = 3)

Output:
0

Explanation:
The string is empty, so there is no non-empty substring to choose.