Home/

...

/

Longest Substring with K Distinct Characters (medium)

Longest Substring with K Distinct Characters (medium)

Problem Statement

Given a string, find the length of the longest substring in it with no more than K distinct characters.

Example 1:

Input: String="araaci", K=2
Output: 4
Explanation: The longest substring with no more than '2' distinct characters is "araa".

Example 2:

Input: String="araaci", K=1
Output: 2
Explanation: The longest substring with no more than '1' distinct characters is "aa".

Example 3:

Input: String="cbbebi", K=3
Output: 5
Explanation: The longest substrings with no more than '3' distinct characters are "cbbeb" & "bbebi".

Example 4:

Input: String="cbbebi", K=10
Output: 6
Explanation: The longest substring with no more than '10' distinct characters is "cbbebi".

Try it yourself

Try solving this question here:

import java.util.*;
class LongestSubstringKDistinct {
  public static int findLength(String str, int k) {
    // TODO: Write your code here
    return -1;
  }
}

Solution

This problem follows the Sliding Window pattern, and we can use a similar dynamic sliding window strategy as discussed in Smallest Subarray With a Greater Sum. We can use a HashMap to remember the frequency ...