Longest Substring with At Most K Distinct Characters

This page explains Java solution to problem `Longest Substring with At Most K Distinct Characters` using `HashMap` data structure.

Problem Statement

Given a string, find the length of the longest substring `T` that contains at most `k` distinct characters.

Example 1:

Input: s = "eceba", k = 2
Output: 3
Explanation: T is "ece" which its length is 3.

Example 2:

Input: s = "aa", k = 1
Output: 2
Explanation: T is "aa" which its length is 2

Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class LongestSubstringWithAtMostKDistinctCharacters {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
HashMap<Character, Integer> map = new HashMap<>();

int right = 0, left = 0, maxLength = 0;
while(right < s.length()) {
char ch = s.charAt(right);
map.put(ch, right++);
if(map.size() == k + 1) {
int index = Collections.min(map.values());
map.remove(s.charAt(index));
left = index + 1;
}
maxLength = Math.max(maxLength, right - left);
}
return maxLength;
}
}

``````

Time Complexity

O(N * log K) Where
N is total number of elements in an input string
K is distinct characters

Space Complexity

O(K) Where
K is distinct characters