Longest Substring with At Most K Distinct Characters
Updated
Problem statement
Given a string s and an integer k, return the length of the longest substring of s that contains at most k different characters.
A substring is a run of characters that are next to each other in s. A substring with fewer than k different characters also counts. If k is 0, only the empty substring qualifies, so the answer is 0.
Function
lengthOfLongestSubstringKDistinct(s: String, k: int) → intExamples
Example 1
s = "eceba"k = 2return = 3The substring ece uses only the two letters e and c, and has length 3. Each substring of length 4 uses more than two letters: eceb uses 3 and ceba uses 4.
Example 2
s = "aabbcc"k = 3return = 6The whole string uses exactly 3 different letters, which is allowed, so the answer is its length, 6.
Example 3
s = "abc"k = 0return = 0With k = 0 no letter may be used, so only the empty substring qualifies and the answer is 0.
Constraints
1 <= s.length <= 5 * 10^4sconsists of lowercase English letters.0 <= k <= 26
More Microsoft Online Assessment questions
- Minimum Cost to Process Priority TasksOA · Seen Nov 2026
- Most Visited Sprint MarkerOA · Seen Nov 2026
- Maximum Escape Game ScoreOA · Seen Nov 2026
- Count Subarrays with a Perfect-Square ProductOA · Seen Nov 2026
- Maximum Interactive Team SizeOA · Seen Nov 2026
- Maximize Pipeline Throughput Under a Scaling BudgetOA · Seen Nov 2026
- Minimum Cost K-Capable ModelsOA · Seen Nov 2026
- Find Available Meeting RoomsOA · Seen Oct 2026
- Maximum Sum of a K-StarOA · Seen Oct 2026
- Capacity to Ship Packages Within DaysOA · ONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Perfect SubstringAXQ Capital · OA
- Longest Distinct StringSuperhuman · OASuperhuman interview questions
- Longest Substring Without Repeating CharactersAkuna Capital · OAAkuna Capital interview questions
- Perfect SubstringsVisa · OAVisa interview questions
- Vowel SubstringSnowflake · OASnowflake interview questions
- Count Distinct Fixed-Length SubstringsAdobe · OAAdobe interview questions
- Video ID Generation (Generic)TikTok · OATikTok interview questions
- Unaligned DedupeRubrik · OARubrik interview questions
- Get Max OccurrencesIBM · OAIBM interview questions
- Find P-Matching ScoreAmazon · OA
Interview reports that mention this question
Microsoft interview experiences
- Microsoft Explore and Student SWE: 12 Experiences (Part 6 of 6)
- Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
- Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
- Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
- Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)