Sliding WindowHardO(n) time · O(1) space

Longest Substring with Same Letters after Replacement

Mahabharata — Drona's Arrow Formation — Converting K Soldiers to Create the Longest Uniform Regiment

K-योधान् परिवर्त्य एकं रूपं प्राप्नुयात्। दीर्घतमं दलं तच्च यत्र शेषाः K मात्राः॥

*By converting K soldiers, one form is achieved. The longest regiment is where the remainder is at most K.*

The Story

Guru Drona surveyed his bowmen. They stood in a line, each labeled either 'A' (Anga archers) or 'B' (Banga archers). The two groups had slightly different arrow styles, and Drona needed the longest contiguous regiment where ALL archers used the SAME style.

He had a special budget: K conversion permits. With each permit, he could retrain one archer from the opposite style to the dominant style of the current regiment. So if the regiment was mostly 'A' archers, up to K 'B' archers could be converted to 'A'. If the regiment was mostly 'B', up to K 'A' archers could be converted.

"The string is `AABABBA`," Ashwatthama reported. "K = 1."

"The question: what is the longest contiguous substring where, after at most K replacements, all characters become the same?"

Ashwatthama thought aloud: "A window of length L with `maxFreq` occurrences of the most frequent character. The number of 'others' that need replacement = L - maxFreq. If L - maxFreq ≤ K, the window is valid."

"Exactly," Drona said. "The window is valid if: `(window_length - max_frequency_in_window) ≤ K`. If this exceeds K, we have too many conversions needed — shrink the window."

Ashwatthama traced through `AABABBA` with K=1:

- right=0 (A): freq[A]=1, maxFreq=1. len=1, 1-1=0≤1 ✓ max=1 - right=1 (A): freq[A]=2, maxFreq=2. len=2, 2-2=0≤1 ✓ max=2 - right=2 (B): freq[A]=2,freq[B]=1, maxFreq=2. len=3, 3-2=1≤1 ✓ max=3 - right=3 (A): freq[A]=3,freq[B]=1, maxFreq=3. len=4, 4-3=1≤1 ✓ max=4 - right=4 (B): freq[A]=3,freq[B]=2, maxFreq=3. len=5, 5-3=2>1 ✗ Shrink! Shrink: remove left=0 (A), freq[A]=2, maxFreq... what is maxFreq now? len=5-1=4 after shrink. 4-3=1≤1 ✓ left=1. len=4, max=4 - right=5 (B): freq[A]=2,freq[B]=3, maxFreq=3. len=5, 5-3=2>1 ✗ Shrink! Remove left=1 (A), freq[A]=1. len=4. 4-3=1≤1 ✓ left=2. len=4, max=4 - right=6 (A): freq[A]=2,freq[B]=3, maxFreq=3. len=5, 5-3=2>1 ✗ Shrink! Remove left=2 (B), freq[B]=2. maxFreq=max(2,2)=2? But freq[A]=2 too. maxFreq stays 3? Wait...

Drona paused and made a crucial observation:

"We never need to DECREASE maxFreq. Even if the element we remove was the most frequent, we keep maxFreq at its highest recorded value. Why? Because if maxFreq decreased, it means the current window is smaller than a window where maxFreq was higher — which would also be valid with the same K. So the only way our answer can IMPROVE is if maxFreq INCREASES. We track the historical maximum."

"So maxFreq only ever increases or stays the same. When the window is invalid (len - maxFreq > K), we simply SLIDE: shrink left by 1, keeping the window size constant. We only grow the window when maxFreq increases."

This is the key insight: `maxFreq` is a monotonically non-decreasing value. We never decrease it. The window either: - Grows (if adding right increases maxFreq, making the window valid at a larger size) - Slides (constant size, when window is invalid but we can't improve maxFreq)

Final answer for `AABABBA`, K=1: **4** (longest valid window).

"The regiment of 4 archers," Drona confirmed, drawing his bow. "With one conversion permit, the longest uniform regiment is 4."

This is the Sliding Window technique for finding the longest substring with same letters after K replacements.

Ashwatthama's First Instinct

For every start-end pair, count the frequency of the most common character. If end-start+1 minus that frequency ≤ K, it's valid. Track the maximum valid length. O(n²) time.

java

public int characterReplacementBruteForce(String s, int k) {
    int maxLen = 0;
    int n = s.length();
    
    for (int start = 0; start < n; start++) {
        int[] freq = new int[26];
        int maxFreq = 0;
        for (int end = start; end < n; end++) {
            freq[s.charAt(end) - 'A']++;
            maxFreq = Math.max(maxFreq, freq[s.charAt(end) - 'A']);
            int windowLen = end - start + 1;
            if (windowLen - maxFreq <= k) {
                maxLen = Math.max(maxLen, windowLen);
            }
        }
    }
    return maxLen;
}

Drona's Wisdom

Drona's key insight: a window is valid if `(length - maxFrequency) ≤ K`. Critical optimization: `maxFreq` is NEVER decreased. We track the historical maximum. When the window becomes invalid, we slide it (shrink left by 1, maintaining window size). The window only GROWS when `maxFreq` increases. This gives us the maximum window size in O(n) — the window size never shrinks, only slides or grows.

java

public int characterReplacement(String s, int k) {
    int[] freq = new int[26];
    int maxFreq = 0;   // Historical maximum — never decreases
    int left = 0;
    int maxLen = 0;
    
    for (int right = 0; right < s.length(); right++) {
        freq[s.charAt(right) - 'A']++;
        maxFreq = Math.max(maxFreq, freq[s.charAt(right) - 'A']);
        
        int windowLen = right - left + 1;
        
        // Window invalid: too many replacements needed
        if (windowLen - maxFreq > k) {
            // Slide: shrink from left (window size stays constant)
            freq[s.charAt(left) - 'A']--;
            left++;
            // Note: we do NOT update maxFreq downward — it's the historical max
        }
        
        maxLen = Math.max(maxLen, right - left + 1);
    }
    
    return maxLen;
}

// Test
public static void main(String[] args) {
    System.out.println(new Solution().characterReplacement("AABABBA", 1));  // 4
    System.out.println(new Solution().characterReplacement("ABAB", 2));     // 4
    System.out.println(new Solution().characterReplacement("AABA", 0));     // 2
}

Step-by-Step Walkthrough

s = "AABABBA",  k = 1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
right=0 (A): freq[A]=1, maxFreq=1. win=1, 1-1=0≤1 ✓. max=1
right=1 (A): freq[A]=2, maxFreq=2. win=2, 2-2=0≤1 ✓. max=2
right=2 (B): freq[B]=1, maxFreq=2. win=3, 3-2=1≤1 ✓. max=3
right=3 (A): freq[A]=3, maxFreq=3. win=4, 4-3=1≤1 ✓. max=4

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
right=4 (B): freq[B]=2, maxFreq=3. win=5, 5-3=2>1 ✗
  Slide: remove left=0(A), freq[A]=2. left=1. win=4. 4-3=1≤1 ✓
  max=4

right=5 (B): freq[B]=3, maxFreq=3. win=5, 5-3=2>1 ✗
  Slide: remove left=1(A), freq[A]=1. left=2. win=4. 4-3=1≤1 ✓
  max=4

right=6 (A): freq[A]=2, maxFreq=3. win=5, 5-3=2>1 ✗
  Slide: remove left=2(B), freq[B]=2. left=3. win=4. 4-3=1≤1 ✓
  max=4

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Return 4

Deep Insight

**Why does not decreasing maxFreq give the correct answer?**

We are looking for the MAXIMUM window length. `maxFreq` represents: "the highest frequency any character achieved in any window we've seen so far." The maximum valid window is `maxFreq + k`. Since we're maximizing, we only care when `maxFreq` increases. When it decreases (a high-frequency char leaves the window), the resulting window (with the old `maxFreq`) would be the same size as before — not larger. So there's no benefit to tracking the decrease.

**The sliding behavior:** When `windowLen - maxFreq > k`, we DON'T shrink (which would lose progress). We SLIDE: remove left, add right, keeping window length constant. The answer can only improve if `maxFreq` increases.

**Why `freq` array of size 26?** The problem only uses uppercase English letters (A-Z). An array lookup is O(1) and faster than a HashMap.

**Edge cases:** - k ≥ n: return n (entire string, replace everything) - All same chars: return n (no replacements needed) - k=0: longest run of any single char

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n²)	O(26) = O(1)	All O(n²) windows checked
Optimal	O(n)	O(26) = O(1)	Single pass; freq array of size 26 is constant space

Pattern Recognition

✅ Longest window where (length - max_frequency) ≤ K
✅ Variable window; grow only when maxFreq increases
✅ maxFreq is monotonically non-decreasing
✅ Slide (don't shrink) on invalid window

**LeetCode Trigger Phrases:**
→ "replace at most k characters"
→ "longest repeating character replacement"
→ "at most k replacements" + maximize length

Bhagavad Gita 3.35

श्रेयान्स्वधर्मो विगुणः परधर्मात्स्वनुष्ठितात्। स्वधर्मे निधनं श्रेयः परधर्मो भयावहः॥

Better is one's own dharma, though imperfectly performed, than the dharma of another well performed. Better is death in one's own dharma; the dharma of another brings fear.

Connection: The algorithm converts a minority of archers (at most K) to match the majority — like temporarily adopting a dharma — but the foundation of the regiment is the dominant type (maxFreq). The insight that maxFreq never decreases mirrors the Gita's teaching: we track the highest dharmic standard achieved and measure all subsequent windows against it. We slide the window without shrinking — preserving the best achievement so far while searching for an even better one.