FastPrepLongest Substring with At Most K Distinct Characters

Longest Substring with At Most K Distinct Characters

Airbnb logoAirbnb● MediumINTERNOA

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) → int

Examples

Example 1

s = "abaccc"k = 2return = 4

The 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 = 2

With 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 = 0

With k = 0, no character is allowed, so only the empty substring works. Its length is 0.

Example 4

s = "abc"k = 5return = 3

The 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 * 104
  • 0 <= k <= 50
  • s contains only lowercase English letters.

More Airbnb Online Assessment questions

Similar questions at other companies

Interview reports that mention this question

Airbnb interview experiences

All Airbnb interview questionsSee Airbnb hiring insights
Saved
class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
      // Write your code here.
    }
}
Checking account…