Longest Substring with K Distinct Characters
Given a string, find the length of the longest substring in it with no more than K
distinct characters.
You can assume that K
is less than or equal to the length of the given string.
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".
fun maxSubArrayLen(target: Int, input: String): Int {
var maxLen = 0
var windowStart = 0
var frequencyMap = HashMap<Char, Int>()
for(windowEnd in 0 until(input.length)) {
frequencyMap[input[windowEnd]] = frequencyMap.getOrDefault(input[windowEnd], 0) + 1
while(frequencyMap.size > target) {
frequencyMap[input[windowStart]] = frequencyMap.getOrDefault(input[windowStart], 0) - 1
if(frequencyMap[input[windowStart]] == 0) {
frequencyMap.remove(input[windowStart])
}
windowStart++
}
maxLen = Math.max(maxLen, windowEnd-windowStart+1)
}
return maxLen
}
- First, we will insert characters from the beginning of the string until we have
K
distinct characters in the HashMap. - These characters will constitute our sliding window. We are asked to find the longest such window having no more than
K
distinct characters. We will remember the length of this window as the longest window so far. - After this, we will keep adding one character in the sliding window (i.e. slide the window ahead) in a stepwise fashion.
- In each step, we will try to shrink the window from the beginning if the count of distinct characters in the HashMap is larger than
K
. We will shrink the window until we have no more thanK
distinct characters in the HashMap. This is needed as we intend to find the longest window. - While shrinking, we’ll decrement the character’s frequency going out of the window and remove it from the HashMap if its frequency becomes zero.
- At the end of each step, we’ll check if the current window length is the longest so far, and if so, remember its length.