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.

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

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

Solution

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