Longest Substring with K Distinct Characters in Java: Explanation & Practice

Find longest substring with at most k distinct characters

Problem summary

Given a string, find the length of the longest substring that contains at most k distinct characters. Use sliding window with HashMap.

Starter code

public class Main {
    public static void main(String[] args) {
        String s = "araaci";
        int k = 2;
        
        // Use HashMap to track character frequencies
        // Expand right, shrink left when distinct > k
        // Print: Length: 4
    }
}

Expected output and test cases

araaci, k=2 → araa
```
Length: 4
```
araaci, k=1 → aa
```
Length: 2
```
cbbebi, k=3 → cbbeb or bbebi
```
Length: 5
```

Hints

Use HashMap to count frequency of each character in window
Expand window by moving right pointer
When distinct chars > k, shrink from left
When shrinking, decrement count; remove from map if count = 0

Related Data Structures & Algorithms exercises

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler