Longest Substring with At Most K Distinct Characters
Updated
Problem statement
You are 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 contiguous, possibly empty, part of the string.
Function
lengthOfLongestSubstringKDistinct(s: String, k: int) → intExamples
Example 1
s = "abaccc"k = 2return = 4The substring "accc" uses only 'a' and 'c', so it has 2 different characters and length 4. Making it longer means adding 'b', which gives 3 different characters. No other substring with at most 2 different characters is longer, so the answer is 4.
Example 2
s = "aabbcc"k = 1return = 2With k = 1, the substring may use only one character. The longest such substrings are "aa", "bb" and "cc", each of length 2.
Example 3
s = "abc"k = 0return = 0With k = 0, no character is allowed, so only the empty substring works. Its length is 0.
Example 4
s = "abc"k = 5return = 3The whole string has only 3 different characters, which is at most 5, so the whole string counts. Its length is 3.
Constraints
1 <= s.length <= 5 * 1040 <= k <= 50scontains only lowercase English letters.
More Airbnb Online Assessment questions
- Task Management SystemOA · Seen Nov 2026
- Recipe Management SystemOA · Seen Nov 2026
- Progressive Banking SystemOA · Seen Nov 2026
- Credit Accounts with Scheduled TransfersOA · Seen Oct 2026
- Parcel Attribute Store with TTLOA · Seen Oct 2026
- Parcel Event TrackingOA · Seen Oct 2026
- Median Home Price by CityOA · Seen Sep 2026
- In-Memory File SystemOA · Seen Sep 2026
- Worker Management (Promotion Track), Part 4: Full-Shift Double PayOA · Seen Sep 2026
- Worker Management (Promotion Track), Part 3: Promotions and SalaryOA · Seen Sep 2026
Similar questions at other companies
- Maximum Valid Substring FrequencyMicrosoft · OAMicrosoft interview questions
- 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
Interview reports that mention this question
Airbnb interview experiences
- Airbnb SWE OA: Four-Level Banking System: 1 Experience
- Airbnb Campus and Full-Time SWE OA / Interviews: 9 Experiences
- Airbnb Intern Phone Interviews: 21 Experiences (Part 7 of 7)
- Airbnb Intern OA and Phone Screens: 17 Experiences (Part 6 of 7)
- Airbnb Intern OA, Diplomacy Game: 19 Experiences (Part 4 of 7)