Longest Substring with At Most K Distinct Characters
In many data processing scenarios, such as log analysis or text parsing, it's often useful to identify patterns within a limited scope. This problem asks you to find the longest segment of text that adheres to a specific constraint: containing no more than a certain number of unique character types. This capability is fundamental for tasks like data compression, feature extraction, or even simple text rendering where character set limitations apply.
Given a string s and an integer k, your task is to find the length of the longest substring T of s such that T contains at most k distinct characters.
s: A string consisting of lowercase English letters.k: An integer representing the maximum number of distinct characters allowed in the substring.s is empty, the length of the longest substring is 0.k is 0: If k is 0, the only valid substring would be an empty one, so the result should be 0.k is large: If k is greater than or equal to the total number of distinct characters in s, then the entire string s is a valid substring, and its length should be returned.s will only contain lowercase English letters ('a' through 'z').Examples
Example 1
Input:
s = "eceba", k = 2
Output:
3
Note:
The longest substring with at most 2 distinct characters is "ece", which has length 3.
Example 2
Input:
s = "aa", k = 1
Output:
2
Note:
The longest substring with at most 1 distinct character is "aa", which has length 2.
Example 3
Input:
s = "abaccc", k = 2
Output:
4
Note:
The longest substring with at most 2 distinct characters is "accc", which has length 4.
Constraints
1 <= s.length <= 5 * 10^40 <= k <= 26s consists of lowercase English letters.k=0.Loading editor...