Longest Substring with K Distinct Characters
Ramayana — Hanuman's Council — The Longest Unbroken Treaty Among K Kingdoms
K-राज्यैः सह सन्धिः स्यात् दीर्घतमः शान्तिमार्गः। अधिके सत्यां अनैक्यं भवति — न्यूनीकरोति पूर्वम्॥
*The longest alliance is with exactly K kingdoms. When more join, unity breaks — release the oldest first.*
The Story
After the great war of Lanka, Rama returned to Ayodhya as emperor. Now began the task of statecraft — building lasting alliances across the subcontinent. Each kingdom was represented by a single letter-symbol carved on the diplomatic scroll.
The scroll of alliances read: `a a b b c c d` — recording each kingdom in the sequence they sent their envoys.
Rama's dilemma: the royal treasury could maintain active diplomatic missions with at most K distinct kingdoms simultaneously. More than K and the treasury was overstretched, protocols broke down, embassies fell silent. He needed to find the longest contiguous stretch of the diplomatic record where at most K distinct kingdoms appeared — the maximum sustained period of balanced diplomacy.
"For K=2," minister Sumantra explained, "we seek the longest window with at most 2 distinct kingdoms."
Hanuman, who had just returned from a diplomatic mission to Lanka, proposed a systematic approach:
"Maintain a sliding window on the scroll. Also maintain a frequency map — a count of how many times each kingdom appears in the current window. The number of KEYS in the map = number of distinct kingdoms in the window."
"Expand the right boundary one envoy at a time, adding their kingdom to the frequency map. If the map size exceeds K, we have too many distinct kingdoms. Shrink from the left: remove the leftmost envoy's kingdom from the frequency map (decrement count, remove the key if count drops to 0). Keep shrinking until map size ≤ K again."
"After each step (whether we expanded or shrank), record the current window length as a candidate maximum."
Sumantra traced through `eceba` with K=2:
- right=0 (e): map={e:1}, size=1 ≤ 2. len=1, max=1 - right=1 (c): map={e:1,c:1}, size=2 ≤ 2. len=2, max=2 - right=2 (e): map={e:2,c:1}, size=2 ≤ 2. len=3, max=3 - right=3 (b): map={e:2,c:1,b:1}, size=3 > 2! Shrink: left=0 (e): count[e]=2→1. Size still 3. left=1. left=1 (c): count[c]=1→0, remove 'c'. map={e:1,b:1}, size=2 ≤ 2. Stop shrinking. left=2. len=3-2+1=2, max=3 - right=4 (a): map={e:1,b:1,a:1}, size=3 > 2! Shrink: left=2 (e): count[e]=1→0, remove 'e'. map={b:1,a:1}, size=2 ≤ 2. Stop. left=3. len=4-3+1=2, max=3
Answer: 3 (the window `ece`).
"The key insight," Hanuman elaborated, "is that the frequency map tells us TWO things at once: the count (needed to know when to remove a key) and the distinct count (map.size(), which is O(1) in Java's HashMap after each operation). We don't need a separate counter for distinct kingdoms."
"What if K=0?" asked Lakshmana.
"Then no non-empty window is valid. Return 0 or -1 depending on problem specification."
"What if K ≥ number of distinct characters in the string?"
"Then the entire string is valid. The window never needs to shrink. Return the string length."
Rama implemented the policy. The longest period of K=2 balanced diplomacy was found in O(n) time. The alliances held for seventeen generations.
"Remember," Hanuman said, "whenever a window constraint involves a COUNT of distinct elements, a frequency map is your tool. The map size tells you the number of distinct items; individual counts tell you when to remove a key."
This is the variable Sliding Window with frequency map for longest substring with K distinct characters.
Sumantra's First Instinct
Try every pair of start and end indices. For each substring, count distinct characters. Track maximum valid length. O(n²) or O(n³) time.
public int longestkSubstrBruteForce(String s, int k) {
int max = 0;
int n = s.length();
for (int start = 0; start < n; start++) {
Set<Character> distinct = new HashSet<>();
for (int end = start; end < n; end++) {
distinct.add(s.charAt(end));
if (distinct.size() > k) break; // Optimization: can't get better
max = Math.max(max, end - start + 1);
}
}
return max == 0 ? -1 : max; // -1 if no valid window exists
}Hanuman's Wisdom
public int longestkSubstr(String s, int k) {
if (k == 0) return -1;
Map<Character, Integer> freq = new HashMap<>();
int left = 0;
int maxLen = -1; // -1 if no valid window found
for (int right = 0; right < s.length(); right++) {
// Add rightmost character to window
char c = s.charAt(right);
freq.merge(c, 1, Integer::sum); // freq[c]++
// Shrink from left until distinct count <= k
while (freq.size() > k) {
char leftChar = s.charAt(left);
freq.merge(leftChar, -1, Integer::sum); // freq[leftChar]--
if (freq.get(leftChar) == 0) {
freq.remove(leftChar); // This distinct char left the window
}
left++;
}
// Valid window: record max length
if (freq.size() == k) {
maxLen = Math.max(maxLen, right - left + 1);
}
}
return maxLen;
}
// Test
public static void main(String[] args) {
System.out.println(new Solution().longestkSubstr("eceba", 2)); // 3 ("ece")
System.out.println(new Solution().longestkSubstr("aa", 1)); // 2 ("aa")
}Step-by-Step Walkthrough
s = "araaci", k = 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
right=0 (a): freq={a:1}, size=1 < 2
right=1 (r): freq={a:1,r:1}, size=2 == k → len=2, max=2
right=2 (a): freq={a:2,r:1}, size=2 → len=3, max=3
right=3 (a): freq={a:3,r:1}, size=2 → len=4, max=4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
right=4 (c): freq={a:3,r:1,c:1}, size=3 > 2!
Shrink: left=0 (a), freq[a]=3→2. size still 3.
Shrink: left=1 (r), freq[r]=1→0, remove 'r'. size=2. left=2.
freq={a:2,c:1}, size=2 → len=4-2+1=3, max=4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
right=5 (i): freq={a:2,c:1,i:1}, size=3 > 2!
Shrink: left=2 (a), freq[a]=2→1. size still 3.
Shrink: left=3 (a), freq[a]=1→0, remove 'a'. size=2. left=4.
freq={c:1,i:1}, size=2 → len=5-4+1=2, max=4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Return 4 ("araa" or "aaac" both have length 4 with 2 distinct chars)Deep Insight
**Why track frequency instead of just a HashSet of distinct chars?**
When we shrink from the left, we need to know if a character is STILL in the window after removing one occurrence. A HashSet would wrongly remove the character even if other occurrences remain. The frequency map counts occurrences; we remove the key only when the count hits 0.
**The pattern: `freq.size()` = distinct count** This is the core insight for all window-with-distinct-count problems. The map's key count IS the distinct count, updated automatically as we add/remove.
**Variant: exactly K distinct vs at most K distinct** - This problem: exactly K distinct (return -1 if never reached k) - Some variants: at most K distinct (valid window when size ≤ k, return 0 if no valid window)
**Edge cases:** - k=0: no valid window (positive-length string can't have 0 distinct chars) - k ≥ alphabet size: entire string is always valid - String with all same chars: window = entire string if k ≥ 1
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(k) | Try all O(n²) windows; HashSet per window tracks distinct chars |
| Optimal | O(n) | O(k) | Each char added and removed once; map has at most k+1 keys |
Pattern Recognition
✅ Substring/subarray problem with a constraint on DISTINCT elements ✅ Maximize window length ✅ Frequency map needed (not just a set) for correct shrinking ✅ Window size is variable **LeetCode Trigger Phrases:** → "longest substring with at most k distinct characters" → "at most k different characters" → "maximize length" + "distinct count constraint"
Bhagavad Gita 5.18
विद्याविनयसंपन्ने ब्राह्मणे गवि हस्तिनि। शुनि चैव श्वपाके च पण्डिताः समदर्शिनः॥
The wise see with equal vision a learned Brahmin, a cow, an elephant, a dog, and a dog-eater.
Connection: The sliding window maintains exactly K distinct 'kingdoms' (characters) in its view at once — treating each character type as an equal contributor to the window's diversity, no more and no less. When a new type enters and exceeds K, the oldest is released — like the wise person who holds equanimity with exactly as much as the situation requires, releasing attachment to the excess. True balance is maintained not through rejection, but through precise, compassionate release.