424. Longest Repeating Character Replacement

Problem Details

• 🔗 Link: https://leetcode.com/problems/longest-repeating-character-replacement/
• 📊 Difficulty: Medium
• 🏷️ Category: Sliding Window
• 💪 Confidence: low

---

📋 Problem Statement

[Insert problem statement here]

Examples

[Insert examples here]

Constraints

[Insert constraints here]

---

📝 Notes from LeetCode

Submission Notes

Submission 1 (java, Runtime: 25 ms)

2 PROBLEMS HERE

37. Longest Substring with At Most K Distinct Characters

🔗 LeetCode Problem: 340. Longest Substring with At Most K Distinct Characters
📊 Difficulty: Medium
🏷️ Topics: Hash Table, String, Sliding Window

Problem Statement

Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.

Example 1:

Input: s = "eceba", k = 2
Output: 3
Explanation: The substring is "ece" with length 3.

Example 2:

Input: s = "aa", k = 1
Output: 2
Explanation: The substring is "aa" with length 2.

Constraints: - 1 <= s.length <= 5 * 10^4 - 0 <= k <= 50

---

🎨 Visual Understanding

The Problem Visualized

s = "eceba", k = 2

All substrings with at most 2 distinct characters:
"e"      → 1 distinct, length 1
"ec"     → 2 distinct, length 2
"ece"    → 2 distinct, length 3 ✓ (longest)
"eceb"   → 3 distinct ✗ (too many)
"c"      → 1 distinct, length 1
"ce"     → 2 distinct, length 2
"ceb"    → 3 distinct ✗
"e"      → 1 distinct, length 1
"eb"     → 2 distinct, length 2
"eba"    → 3 distinct ✗
"b"      → 1 distinct, length 1
"ba"     → 2 distinct, length 2
"a"      → 1 distinct, length 1

Answer: 3 (substring "ece")

Key Observation: Variable Window with Constraint

Use sliding window with character frequency tracking:

Window maintains: "At most k distinct characters"

When distinct count > k:
→ Invalid window, shrink from left

Example: s = "eceba", k = 2

[e c e] → 2 distinct ✓, length 3
[e c e b] → 3 distinct ✗
Shrink: [c e b] → 3 distinct ✗
Shrink: [e b] → 2 distinct ✓, length 2
Continue...

Visual Process

s = "eceba", k = 2

Step 1: [e] → {e:1} → 1 distinct ✓
Step 2: [e c] → {e:1, c:1} → 2 distinct ✓
Step 3: [e c e] → {e:2, c:1} → 2 distinct ✓, max = 3
Step 4: [e c e b] → {e:2, c:1, b:1} → 3 distinct ✗
        Shrink: [c e b] → {c:1, e:1, b:1} → 3 distinct ✗
        Shrink: [e b] → {e:1, b:1} → 2 distinct ✓
Step 5: [e b a] → {e:1, b:1, a:1} → 3 distinct ✗
        Shrink: [b a] → {b:1, a:1} → 2 distinct ✓

Maximum length: 3

---

🎯 Approach 1: Brute Force

The Most Natural Thinking 💭

Core Logic:

Check all substrings:
1. For each starting position i
2. For each ending position j
3. Count distinct characters in s[i...j]
4. If distinct <= k, record length
5. Return maximum length

Why This Works: - Checks all possibilities - Guaranteed to find answer - Easy to understand

Why This Fails Requirements: - Time complexity O(n²) or O(n³) - Counting distinct chars repeatedly - Too slow for large strings - Not optimal for interviews

Implementation

public int lengthOfLongestSubstringKDistinct(String s, int k) {
    int n = s.length();
    int maxLen = 0;

    for (int i = 0; i < n; i++) {
        Set<Character> distinct = new HashSet<>();

        for (int j = i; j < n; j++) {
            distinct.add(s.charAt(j));

            if (distinct.size() <= k) {
                maxLen = Math.max(maxLen, j - i + 1);
            } else {
                break;  // Too many distinct chars
            }
        }
    }

    return maxLen;
}

⏰ Time: O(n²) - for each start, expand until k+1 distinct
💾 Space: O(k) - HashSet for distinct characters

---

✅ Approach 2: Sliding Window with HashMap (Optimal)

The Breakthrough Insight 💡

Core Logic:

Use variable-size sliding window with HashMap:

HashMap: character → frequency in current window

1. Expand window: Add right character
2. If distinct > k: Shrink from left until distinct <= k
3. Track maximum length
4. Repeat until right reaches end

Key insight: HashMap size = number of distinct characters

Visual Explanation:

s = "eceba", k = 2

Step 1: [e]
        map = {e:1}, distinct = 1 <= 2 ✓
        maxLen = 1

Step 2: [e c]
        map = {e:1, c:1}, distinct = 2 <= 2 ✓
        maxLen = 2

Step 3: [e c e]
        map = {e:2, c:1}, distinct = 2 <= 2 ✓
        maxLen = 3

Step 4: [e c e b]
        map = {e:2, c:1, b:1}, distinct = 3 > 2 ✗

        Shrink:
        Remove 'e': map = {e:1, c:1, b:1}, distinct = 3
        Remove 'c': map = {e:1, b:1}, distinct = 2 ✓
        Window: [e b]

Step 5: [e b a]
        map = {e:1, b:1, a:1}, distinct = 3 > 2 ✗

        Shrink:
        Remove 'e': map = {b:1, a:1}, distinct = 2 ✓
        Window: [b a]

Final: maxLen = 3

Why This Works:

Sliding window maintains invariant:
"At most k distinct characters in window"

When distinct > k:
- Shrink from left until distinct <= k
- Each character visited at most twice
- Total time: O(n)

HashMap tracks:
- Which characters are in window
- Frequency of each character
- When frequency becomes 0, remove from map

Implementation

public int lengthOfLongestSubstringKDistinct(String s, int k) {
    if (s == null || s.length() == 0 || k == 0) {
        return 0;
    }

    int n = s.length();
    Map<Character, Integer> window = new HashMap<>();
    int left = 0;
    int maxLen = 0;

    for (int right = 0; right < n; right++) {
        // Expand window: add right character
        char rightChar = s.charAt(right);
        window.put(rightChar, window.getOrDefault(rightChar, 0) + 1);

        // Shrink window while distinct > k
        while (window.size() > k) {
            char leftChar = s.charAt(left);
            window.put(leftChar, window.get(leftChar) - 1);

            // Remove character if count becomes 0
            if (window.get(leftChar) == 0) {
                window.remove(leftChar);
            }

            left++;
        }

        // Update maximum length
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
}

⏰ Time: O(n) - each character visited at most twice
💾 Space: O(k) - HashMap stores at most k+1 characters

---

🔍 Step-by-Step Execution

Example: s = "eceba", k = 2

Initial State:
═══════════════════════════════════════════════════════════════════
s = "eceba"
k = 2
left = 0, maxLen = 0
window = {}


Step 1: right = 0, char = 'e'
═══════════════════════════════════════════════════════════════════
Add 'e': window = {e:1}
Distinct count = 1 <= 2 ✓

Window: [e]
maxLen = max(0, 0-0+1) = 1

left = 0, maxLen = 1


Step 2: right = 1, char = 'c'
═══════════════════════════════════════════════════════════════════
Add 'c': window = {e:1, c:1}
Distinct count = 2 <= 2 ✓

Window: [e c]
maxLen = max(1, 1-0+1) = 2

left = 0, maxLen = 2


Step 3: right = 2, char = 'e'
═══════════════════════════════════════════════════════════════════
Add 'e': window = {e:2, c:1}
Distinct count = 2 <= 2 ✓

Window: [e c e]
maxLen = max(2, 2-0+1) = 3

left = 0, maxLen = 3


Step 4: right = 3, char = 'b'
═══════════════════════════════════════════════════════════════════
Add 'b': window = {e:2, c:1, b:1}
Distinct count = 3 > 2 ✗

Need to shrink:

Shrink iteration 1:
  Remove s[0]='e': window = {e:1, c:1, b:1}
  e count = 1 (not 0, don't remove)
  left = 1
  Distinct count = 3 > 2 ✗, continue shrinking

Shrink iteration 2:
  Remove s[1]='c': window = {e:1, b:1}
  c count = 0, remove from map
  left = 2
  Distinct count = 2 <= 2 ✓, stop shrinking

Window: [e b]
maxLen = max(3, 3-2+1) = 3 (no change)

left = 2, maxLen = 3


Step 5: right = 4, char = 'a'
═══════════════════════════════════════════════════════════════════
Add 'a': window = {e:1, b:1, a:1}
Distinct count = 3 > 2 ✗

Need to shrink:

Shrink iteration 1:
  Remove s[2]='e': window = {b:1, a:1}
  e count = 0, remove from map
  left = 3
  Distinct count = 2 <= 2 ✓, stop shrinking

Window: [b a]
maxLen = max(3, 4-3+1) = 3 (no change)

left = 3, maxLen = 3


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: 3
═══════════════════════════════════════════════════════════════════

Another Example: s = "aa", k = 1

Step 1: right=0, 'a'
        window = {a:1}, distinct = 1 ≤ 1 ✓
        maxLen = 1

Step 2: right=1, 'a'
        window = {a:2}, distinct = 1 ≤ 1 ✓
        maxLen = 2

Result: 2

---

🔍 Edge Cases

Case 1: k = 0
Input: s = "abc", k = 0
Output: 0
Explanation: Cannot have any characters

Case 2: k >= distinct characters in s
Input: s = "abc", k = 5
Output: 3
Explanation: Entire string has only 3 distinct chars

Case 3: All same characters
Input: s = "aaaa", k = 1
Output: 4
Explanation: Entire string

Case 4: k = 1
Input: s = "abcba", k = 1
Output: 1
Explanation: Any single character

Case 5: Alternating characters
Input: s = "ababab", k = 2
Output: 6
Explanation: Entire string has 2 distinct chars

Case 6: Single character string
Input: s = "a", k = 1
Output: 1

Case 7: Complex pattern
Input: s = "aabbcc", k = 2
Output: 4
Explanation: "aabb" or "bbcc"

Case 8: No repeating characters
Input: s = "abcdef", k = 3
Output: 3
Explanation: "abc" or "bcd" or "cde" or "def"

---

Common Mistakes

Mistake 1: Not removing character when count becomes 0
❌ Wrong: 
    window.put(leftChar, window.get(leftChar) - 1);
    // Forgot to remove when count = 0
✓ Right: 
    window.put(leftChar, window.get(leftChar) - 1);
    if (window.get(leftChar) == 0) {
        window.remove(leftChar);
    }
Reason: HashMap size must equal distinct count

Mistake 2: Using if instead of while for shrinking
❌ Wrong: 
    if (window.size() > k) {
        // Remove once
    }
✓ Right: 
    while (window.size() > k) {
        // Keep removing until valid
    }
Reason: May need to remove multiple characters

Mistake 3: Not handling k = 0
❌ Wrong: 
    // No check for k = 0
✓ Right: 
    if (k == 0) return 0;
Reason: Cannot have any characters when k = 0

Mistake 4: Updating maxLen inside while loop
❌ Wrong: 
    while (window.size() > k) {
        maxLen = Math.max(maxLen, right - left + 1);
        // shrink...
    }
✓ Right: 
    while (window.size() > k) {
        // shrink...
    }
    maxLen = Math.max(maxLen, right - left + 1);
Reason: Update only when window is valid

Mistake 5: Wrong distinct count check
❌ Wrong: 
    if (window.values().stream().distinct().count() > k) {
        // Very inefficient!
    }
✓ Right: 
    if (window.size() > k) {
        // HashMap size = distinct count
    }
Reason: HashMap size directly gives distinct count

Mistake 6: Not handling null or empty string
❌ Wrong: 
    int n = s.length();  // NPE if s is null
✓ Right: 
    if (s == null || s.length() == 0) return 0;
Reason: Need to check edge cases

---

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force
  Time: O(n²)
  Space: O(k)
  Use: Only for understanding

Approach 2: Sliding Window + HashMap (RECOMMENDED)
  Time: O(n)
  Space: O(k)
  Use: Optimal solution, best for interviews

🔑 The Core Insight

Variable-Size Sliding Window with Constraint:

Key Invariant:
"Window has at most k distinct characters"

Data Structure:
HashMap: character → frequency
- HashMap.size() = number of distinct characters
- When frequency becomes 0, remove from map

Decision Logic:
- window.size() <= k → Valid, expand
- window.size() > k → Invalid, shrink

Algorithm:
1. Expand: Add character to window
2. While distinct > k:
   - Shrink: Remove from left
   - Decrement frequency
   - If frequency = 0, remove from map
3. Update maximum length

Time Complexity:
- Each character added once (right pointer)
- Each character removed at most once (left pointer)
- Total: O(n)

Template for "At Most K" Problems:
1. Use HashMap to track frequency
2. Expand window unconditionally
3. Shrink while constraint violated
4. Update result after shrinking

🎯 Pattern Recognition

Problem Type: Longest Substring with Character Constraint
Core Pattern: Variable-Size Sliding Window + HashMap

When to Apply:
✓ Finding substring with character constraints
✓ "At most K distinct/unique" pattern
✓ Need to track character frequencies
✓ Want O(n) time complexity

Key Techniques:
→ Variable-size sliding window
→ HashMap for character frequency
→ Expand always, shrink when constraint violated
→ HashMap.size() = distinct count
→ Remove from map when frequency = 0

Variations:
- At most K distinct → this problem
- Exactly K distinct → shrink if < k or > k
- At least K distinct → different approach

Related Problems:
- Longest Substring Without Repeating Characters (LC 3) - k=size
- Longest Substring with At Most Two Distinct Characters (LC 159) - k=2
- Fruit Into Baskets (LC 904) - k=2
- Subarrays with K Different Integers (LC 992)

🧠 Interview Strategy

Step 1: "Need longest substring with at most k distinct chars"
Step 2: "Use sliding window with HashMap"
Step 3: "HashMap tracks frequency, size = distinct count"
Step 4: "Expand always, shrink when distinct > k"
Step 5: "O(n) time, O(k) space"

Key Points to Mention:
- Variable-size sliding window
- HashMap for frequency tracking
- HashMap.size() gives distinct count
- Shrink while distinct > k
- Remove from map when frequency = 0
- Update maxLen after shrinking
- O(n) time, each char visited twice max
- O(k) space for HashMap

---

📝 Quick Revision Notes

🎯 Core Concept:

Variable-size sliding window with HashMap for frequency. Keep at most k distinct characters. Expand always, shrink while distinct > k.

⚡ Quick Implementation:

import java.util.HashMap;

class Test {
  public int lengthOfLongestSubstringKDistinct(String s, int k) {
    int res = Integer.MIN_VALUE;
    int len = s.length();
    int left = 0;
    int right = 0;

    // Map that stores frequencies of chars.
    HashMap<Character, Integer> map = new HashMap<>();

    while (right < len) {
      char ch = s.charAt(right);
      map.put(ch, map.getOrDefault(ch, 0) + 1);

      // If still map holds less than k chars, update res.
      if (map.size() <= k) {
        res = Math.max(res, right - left + 1);
      } else {
        // shrink window from left till map size becomes <= k
        while (left <= right && map.size() > k) {
          // reduce freq count and check if its 0, remove that char
          char leftCharToRemove = s.charAt(left);
          map.put(leftCharToRemove, map.get(leftCharToRemove) - 1);
          if (map.get(leftCharToRemove) == 0) {
            map.remove(leftCharToRemove);
          }

          // move left pointer by 1.
          left++;
        }
      }

      right++;
    }

    return res == Integer.MIN_VALUE ? 0 : res;
  }

  public static void main(String[] args) {
    Test t = new Test();
    System.out.println(t.lengthOfLongestSubstringKDistinct("eceba", 2));
    System.out.println(t.lengthOfLongestSubstringKDistinct("aa", 1));
    System.out.println(t.lengthOfLongestSubstringKDistinct("abc", 0));
    System.out.println(t.lengthOfLongestSubstringKDistinct("abc", 5));

    System.out.println(t.lengthOfLongestSubstringKDistinct("aaaa", 1));
    System.out.println(t.lengthOfLongestSubstringKDistinct("abcba", 1));
    System.out.println(t.lengthOfLongestSubstringKDistinct("ababab", 2));
    System.out.println(t.lengthOfLongestSubstringKDistinct("a", 1));

    System.out.println(t.lengthOfLongestSubstringKDistinct("aabbcc", 2));
    System.out.println(t.lengthOfLongestSubstringKDistinct("abcdef", 3));
  }
}

🔑 Key Insights:

• HashMap: character → frequency in window
• Distinct count: HashMap.size()
• Expand: Always add right character
• Shrink: While window.size() > k
• Remove from map: When frequency becomes 0
• Update maxLen: After shrinking (when window valid)
• Use while: Not if, for shrinking
• Time: O(n) - each char visited at most twice
• Space: O(k) - at most k+1 characters in HashMap
• Edge case: Handle k=0, return 0

🎪 Memory Aid:

"HashMap SIZE = DISTINCT! Expand always, shrink when OVER k!"
Think: "At most k distinct: expand, shrink, track max"

---

Related Patterns

• Longest Substring Without Repeating Characters (LC 3)
• Longest Substring with At Most Two Distinct Characters (LC 159)
• Fruit Into Baskets (LC 904)
• Subarrays with K Different Integers (LC 992)

---

Happy practicing! 🎯

38. Longest Repeating Character Replacement

🔗 LeetCode Problem: 424. Longest Repeating Character Replacement
📊 Difficulty: Medium
🏷️ Topics: Hash Table, String, Sliding Window

Problem Statement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa to make "AAAA" or "BBBB".

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
There may exists other ways to achieve this answer too.

Constraints: - 1 <= s.length <= 10^5 - s consists of only uppercase English letters. - 0 <= k <= s.length

---

🎨 Visual Understanding

The Problem Visualized

s = "AABABBA", k = 1

We can replace at most 1 character.

Option 1: Make all 'B's
"AABABBA"
 ^       → Replace this 'A' with 'B'
"ABABBBA" → Substring "BBBB" (length 4) ✓

Option 2: Make all 'A's
"AABABBA"
    ^    → Replace this 'B' with 'A'
"AAAAABA" → Substring "AAAA" (length 4) ✓

Answer: 4

Key Observation: Window Validity Formula

A valid window can be formed if:
windowLength - maxFrequency <= k

Why?
- windowLength = total characters in window
- maxFrequency = count of most frequent character
- windowLength - maxFrequency = characters to replace
- If replacements needed ≤ k, window is valid

Example:
Window = "AABA", k = 1
windowLength = 4
maxFrequency = 3 (three 'A's)
replacements = 4 - 3 = 1 ≤ 1 ✓ Valid!

Window = "AABAB", k = 1
windowLength = 5
maxFrequency = 3 (three 'A's)
replacements = 5 - 3 = 2 > 1 ✗ Invalid!

Visual Process

s = "AABABBA", k = 1

[A] → len=1, maxFreq=1, replace=0 ≤ 1 ✓
[A A] → len=2, maxFreq=2, replace=0 ≤ 1 ✓
[A A B] → len=3, maxFreq=2, replace=1 ≤ 1 ✓
[A A B A] → len=4, maxFreq=3, replace=1 ≤ 1 ✓, max=4
[A A B A B] → len=5, maxFreq=3, replace=2 > 1 ✗
Shrink: [A B A B] → len=4, maxFreq=3(historical), replace=1 ≤ 1 ✓
[B A B B] → len=4, maxFreq=3, replace=1 ≤ 1 ✓, max=4
...continue

Maximum length: 4

---

🎯 Approach 1: Brute Force

The Most Natural Thinking 💭

Core Logic:

Check all substrings:
1. For each starting position i
2. For each ending position j
3. Count frequency of each character
4. Find max frequency
5. If windowLength - maxFreq <= k, valid
6. Track maximum length

Why This Works: - Checks all possibilities - Guaranteed to find answer - Easy to understand

Why This Fails Requirements: - Time complexity O(n² × 26) = O(n²) - Recounts frequencies for overlapping windows - Too slow for large strings - Not optimal for interviews

Implementation

public int characterReplacement(String s, int k) {
    int n = s.length();
    int maxLen = 0;

    for (int i = 0; i < n; i++) {
        int[] count = new int[26];
        int maxFreq = 0;

        for (int j = i; j < n; j++) {
            count[s.charAt(j) - 'A']++;
            maxFreq = Math.max(maxFreq, count[s.charAt(j) - 'A']);

            int windowLen = j - i + 1;
            if (windowLen - maxFreq <= k) {
                maxLen = Math.max(maxLen, windowLen);
            }
        }
    }

    return maxLen;
}

⏰ Time: O(n²) - for each start, expand and count
💾 Space: O(1) - array of size 26

---

✅ Approach 2: Sliding Window with Historical maxFreq (Optimal)

The Breakthrough Insight 💡

Core Logic:

Use variable-size sliding window with frequency array:

Valid window condition:
windowLength - maxFrequency <= k

BRILLIANT OPTIMIZATION:
We DON'T need to recalculate maxFrequency after shrinking!
We can use HISTORICAL maximum (max seen so far)

Algorithm:
1. Expand window: Add right character
2. Update maxFrequency (only if current char freq > maxFreq)
3. If invalid (windowLength - maxFreq > k):
   - Shrink from left
   - DON'T recalculate maxFreq (use historical max)
4. Track maximum length

Key insight: Historical maxFreq acts as a filter -
only windows with higher maxFreq can beat our current best!

🔬 Why Historical maxFreq Works - Detailed Proof

The Question: After shrinking, the actual maxFreq in the current window might be lower. Why can we keep using the old (higher) maxFreq value?

The Answer: Because we're finding the LONGEST substring, and historical maxFreq naturally filters out windows that can't beat our current best.

Mathematical Proof:

Given:
- We found a valid window: length = L, maxFreq = M
- This window satisfies: L - M ≤ k

To beat this result, we need:
- New window with length > L

For a window of length (L+1) to be valid:
(L+1) - newMaxFreq ≤ k
(L+1) - newMaxFreq ≤ (L - M)    [since k ≥ L - M]
newMaxFreq ≥ (L+1) - (L - M)
newMaxFreq ≥ M + 1

Conclusion: To beat length L, we MUST have maxFreq ≥ M + 1

What This Means: - If we keep historical maxFreq = M - A window of length L with actual maxFreq < M will fail the check - Only when we find actual maxFreq ≥ M + 1, we pass the check - This automatically happens when we add a character with higher frequency!

Visual Example:

Step 1: Found valid window
═══════════════════════════════════════════════════════════════
Window: [A A B A]
count = {A:3, B:1}
maxFreq = 3  ← Best frequency seen
windowLen = 4
replacements = 4 - 3 = 1 ≤ 1 ✓
maxLen = 4  ← Current best length


Step 2: Expand and become invalid
═══════════════════════════════════════════════════════════════
Window: [A A B A B]
count = {A:3, B:2}
maxFreq = 3  ← Still 3 (historical)
windowLen = 5
replacements = 5 - 3 = 2 > 1 ✗ Invalid!


Step 3: Shrink
═══════════════════════════════════════════════════════════════
Remove 'A': Window becomes [A B A B]
count = {A:2, B:2}

ACTUAL maxFreq in window = 2 (both A and B appear 2 times)
But we KEEP maxFreq = 3 (historical)

Check with historical maxFreq = 3:
windowLen = 4
replacements = 4 - 3 = 1 ≤ 1 ✓ "Valid"

But wait! Actual replacements needed = 4 - 2 = 2 > 1 ✗

Isn't this wrong?


Step 4: Understanding Why It's Actually Correct
═══════════════════════════════════════════════════════════════
The algorithm says: "This window passes the check"
But it doesn't update maxLen because:
  maxLen = max(4, 4) = 4 (no improvement)

Why use historical max = 3 when actual is 2?
Because:
  - We already found length 4 with maxFreq = 3
  - Current window length 4 with actual maxFreq = 2 is WORSE
  - It can't beat our existing result
  - We're only looking for BETTER windows

The filter works:
  - Historical maxFreq = 3 says: "I've seen better"
  - Current window with maxFreq = 2 can't beat previous
  - Only windows with maxFreq ≥ 4 can give us length > 4


Step 5: What happens when we find better?
═══════════════════════════════════════════════════════════════
Later, if we encounter:
Window: [B B B B B]
count = {B:5}
maxFreq gets updated to 5  ← Naturally updated!
windowLen = 5
replacements = 5 - 5 = 0 ≤ 1 ✓
maxLen = max(4, 5) = 5  ← New best!

When we add characters with higher frequency,
maxFreq updates automatically!

🎯 The "Lazy Evaluation" Principle

Think of historical maxFreq as a checkpoint:

Checkpoint (maxFreq = 3):
  "I found length 4 with a character appearing 3 times"
  "Only tell me about windows where a character appears ≥ 4 times"
  "Those are the only ones that can beat my current best"

When checking new windows:
  - Window with maxFreq = 2: "Not interested, can't beat checkpoint"
  - Window with maxFreq = 3: "Same as checkpoint, no improvement"
  - Window with maxFreq = 4: "Now we're talking! Update checkpoint!"

🏃 Why We Don't Need Recalculation

Without Recalculation (Our Approach):

while (windowLen - maxFreq > k) {
    count[s.charAt(left) - 'A']--;
    left++;
    windowLen--;
    // DON'T recalculate maxFreq
    // Historical max acts as filter
}

- Simple code - Faster: O(1) per shrink operation - Correct answer

With Recalculation (Unnecessary):

while (windowLen - maxFreq > k) {
    count[s.charAt(left) - 'A']--;
    left++;
    windowLen--;

    // Recalculate maxFreq (O(26) work)
    maxFreq = 0;
    for (int i = 0; i < 26; i++) {
        maxFreq = Math.max(maxFreq, count[i]);
    }
}

- Complex code - Slower: O(26) per shrink operation - Same answer (proven to be equivalent!)

Both give identical results! Historical max is just more efficient.

Implementation

public int characterReplacement(String s, int k) {
    int[] count = new int[26];
    int left = 0;
    int maxFreq = 0;  // Historical maximum frequency
    int maxLen = 0;

    for (int right = 0; right < s.length(); right++) {
        // Expand window: add right character
        count[s.charAt(right) - 'A']++;

        // Update maxFreq (only increases, never decreases)
        maxFreq = Math.max(maxFreq, count[s.charAt(right) - 'A']);

        // Check if window is valid
        int windowLen = right - left + 1;

        // If invalid, shrink window
        // Note: We DON'T recalculate maxFreq here!
        while (windowLen - maxFreq > k) {
            count[s.charAt(left) - 'A']--;
            left++;
            windowLen = right - left + 1;
        }

        // Update maximum length
        maxLen = Math.max(maxLen, windowLen);
    }

    return maxLen;
}

⏰ Time: O(n) - each character visited at most twice
💾 Space: O(1) - array of size 26

---

🔍 Step-by-Step Execution with Historical maxFreq Explanation

Example: s = "AABABBA", k = 1

Initial State:
═══════════════════════════════════════════════════════════════════
s = "AABABBA"
k = 1
left = 0, maxFreq = 0, maxLen = 0
count = [0, 0, ..., 0]  (26 zeros)


Step 1: right = 0, char = 'A'
═══════════════════════════════════════════════════════════════════
Add 'A': count[0] = 1
maxFreq = max(0, 1) = 1

windowLen = 0 - 0 + 1 = 1
replacements = 1 - 1 = 0 ≤ 1 ✓ Valid

maxLen = max(0, 1) = 1

Window: [A]
💡 Historical maxFreq = 1


Step 2: right = 1, char = 'A'
═══════════════════════════════════════════════════════════════════
Add 'A': count[0] = 2
maxFreq = max(1, 2) = 2  ← Updated to 2

windowLen = 1 - 0 + 1 = 2
replacements = 2 - 2 = 0 ≤ 1 ✓ Valid

maxLen = max(1, 2) = 2

Window: [A A]
💡 Historical maxFreq = 2


Step 3: right = 2, char = 'B'
═══════════════════════════════════════════════════════════════════
Add 'B': count[1] = 1
maxFreq = max(2, 1) = 2  ← Stays 2 (historical max)

windowLen = 2 - 0 + 1 = 3
replacements = 3 - 2 = 1 ≤ 1 ✓ Valid

maxLen = max(2, 3) = 3

Window: [A A B]
💡 Historical maxFreq = 2


Step 4: right = 3, char = 'A'
═══════════════════════════════════════════════════════════════════
Add 'A': count[0] = 3
maxFreq = max(2, 3) = 3  ← Updated to 3

windowLen = 3 - 0 + 1 = 4
replacements = 4 - 3 = 1 ≤ 1 ✓ Valid

maxLen = max(3, 4) = 4

Window: [A A B A]
💡 Historical maxFreq = 3 (new peak!)


Step 5: right = 4, char = 'B'
═══════════════════════════════════════════════════════════════════
Add 'B': count[1] = 2
maxFreq = max(3, 2) = 3  ← Stays 3 (historical max)

windowLen = 4 - 0 + 1 = 5
replacements = 5 - 3 = 2 > 1 ✗ Invalid!

Need to shrink:
  Remove s[0]='A': count[0] = 2
  left = 1
  windowLen = 4 - 1 + 1 = 4

  Check again: 4 - 3 = 1 ≤ 1 ✓ Valid now

maxLen = max(4, 4) = 4  ← No improvement

Window: [A B A B]
count = {A:2, B:2}
💡 ACTUAL maxFreq in current window = 2
💡 But we KEEP historical maxFreq = 3

🔍 Why is this OK?
   - We found length 4 with maxFreq = 3
   - Current length 4 with actual maxFreq = 2 is worse
   - Historical max = 3 acts as a filter
   - We need maxFreq ≥ 4 to beat our best (length 4)


Step 6: right = 5, char = 'B'
═══════════════════════════════════════════════════════════════════
Add 'B': count[1] = 3
maxFreq = max(3, 3) = 3  ← Stays 3

windowLen = 5 - 1 + 1 = 5
replacements = 5 - 3 = 2 > 1 ✗ Invalid!

Need to shrink:
  Remove s[1]='A': count[0] = 1
  left = 2
  windowLen = 5 - 2 + 1 = 4

  Check again: 4 - 3 = 1 ≤ 1 ✓ Valid now

maxLen = max(4, 4) = 4

Window: [B A B B]
count = {A:1, B:3}
💡 ACTUAL maxFreq = 3 (three B's)
💡 Historical maxFreq = 3
   This time they match!


Step 7: right = 6, char = 'A'
═══════════════════════════════════════════════════════════════════
Add 'A': count[0] = 2
maxFreq = max(3, 2) = 3  ← Stays 3

windowLen = 6 - 2 + 1 = 5
replacements = 5 - 3 = 2 > 1 ✗ Invalid!

Need to shrink:
  Remove s[2]='B': count[1] = 2
  left = 3
  windowLen = 6 - 3 + 1 = 4

  Check again: 4 - 3 = 1 ≤ 1 ✓ Valid now

maxLen = max(4, 4) = 4

Window: [A B B A]
count = {A:2, B:2}
💡 ACTUAL maxFreq = 2
💡 Historical maxFreq = 3 (still using old value)


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: 4
═══════════════════════════════════════════════════════════════════

Key Observations:
1. maxFreq only increased (1→2→3), never decreased
2. After peak (maxFreq=3), we kept using this historical value
3. Windows with actual maxFreq < 3 couldn't improve maxLen
4. Algorithm still found correct answer!

---

🔍 Edge Cases

Case 1: k = 0 (no replacements)
Input: s = "AABBB", k = 0
Output: 3
Explanation: Longest substring without replacement is "BBB"

Case 2: k >= s.length (replace everything)
Input: s = "ABCD", k = 5
Output: 4
Explanation: Can make entire string same character

Case 3: All same characters
Input: s = "AAAA", k = 2
Output: 4
Explanation: Already all same

Case 4: k = s.length
Input: s = "ABCD", k = 4
Output: 4
Explanation: Replace all to same character

Case 5: Alternating characters
Input: s = "ABABAB", k = 2
Output: 5
Explanation: "AAAAB" or "BABBB"

Case 6: Single character
Input: s = "A", k = 1
Output: 1

Case 7: All different characters
Input: s = "ABCDEF", k = 2
Output: 3
Explanation: Pick any char and replace 2 others

Case 8: Large k
Input: s = "AABA", k = 10
Output: 4
Explanation: k larger than needed

---

Common Mistakes

Mistake 1: Not updating maxFreq correctly
❌ Wrong: 
    maxFreq = count[s.charAt(right) - 'A'];  // Overwrite, not max
✓ Right: 
    maxFreq = Math.max(maxFreq, count[s.charAt(right) - 'A']);
Reason: Need maximum frequency seen, not just current

Mistake 2: Recalculating maxFreq after shrinking (unnecessary)
❌ Wrong (but still works, just slower): 
    while (...) {
        count[s.charAt(left) - 'A']--;
        left++;
        maxFreq = 0;  // Recalculate O(26)
        for (int i = 0; i < 26; i++) {
            maxFreq = Math.max(maxFreq, count[i]);
        }
    }
✓ Right (optimal): 
    while (...) {
        count[s.charAt(left) - 'A']--;
        left++;
        // No need to recalculate maxFreq!
    }
Reason: Historical max is sufficient and more efficient

Mistake 3: Wrong validity check
❌ Wrong: 
    if (windowLen - count[s.charAt(right) - 'A'] <= k) {
        // Using current char frequency, not max
    }
✓ Right: 
    if (windowLen - maxFreq <= k) {
        // Using max frequency in window
    }
Reason: Need most frequent char, not just current char

Mistake 4: Using if instead of while for shrinking
❌ Wrong: 
    if (windowLen - maxFreq > k) {
        // Shrink once
    }
✓ Right: 
    while (windowLen - maxFreq > k) {
        // Keep shrinking until valid
    }
Reason: May need multiple shrinks

Mistake 5: Not handling k = 0
❌ Wrong: 
    // Assuming k > 0
✓ Right: 
    // Algorithm works for k = 0 naturally
Reason: When k=0, finds longest substring of same char

Mistake 6: Updating maxLen inside while loop
❌ Wrong: 
    while (windowLen - maxFreq > k) {
        maxLen = Math.max(maxLen, windowLen);
        // shrink...
    }
✓ Right: 
    while (windowLen - maxFreq > k) {
        // shrink...
    }
    maxLen = Math.max(maxLen, windowLen);
Reason: Update only when window is valid

---

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force
  Time: O(n²)
  Space: O(1)
  Use: Only for understanding

Approach 2: Sliding Window with Historical maxFreq (RECOMMENDED)
  Time: O(n)
  Space: O(1)
  Use: Optimal solution, best for interviews

🔑 The Core Insight

Valid Window Formula:
windowLength - maxFrequency <= k

Interpretation:
- windowLength: total characters in window
- maxFrequency: count of most frequent character
- windowLength - maxFrequency: chars to replace
- If replacements needed ≤ k → valid window

Example:
Window = "AAAB", k = 1
- Length = 4
- maxFreq = 3 (three A's)
- Replace = 4 - 3 = 1 ≤ 1 ✓
- Can replace 1 'B' to make "AAAA"


🌟 BRILLIANT OPTIMIZATION - Historical maxFreq:

Instead of recalculating maxFreq after every shrink,
we keep the HISTORICAL MAXIMUM (highest value seen so far)

Why This Works:
═══════════════════════════════════════════════════════════════

1. We're finding LONGEST substring (maximization)

2. Only care about windows that BEAT current best

3. Mathematical Proof:
   - Found valid window: length L with maxFreq = M
   - To beat it, need length > L
   - For length (L+1) to be valid: (L+1) - maxFreq ≤ k
   - This requires: maxFreq ≥ M + 1
   - So we NEED higher frequency to beat current best!

4. Historical max = M acts as FILTER:
   - Windows with actual maxFreq < M can't beat best
   - Windows with actual maxFreq = M give same length
   - Only maxFreq > M can give longer length
   - When we find freq > M, maxFreq updates automatically!

5. Time Complexity:
   - Without recalc: O(n) - single pass
   - With recalc: O(n × 26) - still O(n) but slower


The "Lazy Evaluation" Principle:
═══════════════════════════════════════════════════════════════

Think of maxFreq as a checkpoint:
  "I found length 4 with maxFreq = 3"
  "Only tell me about windows with maxFreq ≥ 4"
  "Those are the only ones that can beat my record"

When actual maxFreq drops after shrinking:
  - Historical maxFreq says "not good enough"
  - Window might pass validation but won't update maxLen
  - This is intentional - filtering out worse windows
  - Only when we find better frequency, we progress


Visual Timeline:
═══════════════════════════════════════════════════════════════

maxFreq:  1 → 2 → 2 → 3 → 3 → 3 → 3 → 3 → 4
Window:   A   AA  AAB AABA ↑              ↑
                           keeps 3      found 4!

Only increases, never decreases!
Acts as filter for finding better windows.

🎯 Pattern Recognition

Problem Type: Longest Substring with Replacement Constraint
Core Pattern: Variable-Size Sliding Window + Frequency Array

When to Apply:
✓ Finding longest substring with replacements
✓ "At most k replacements" pattern
✓ Need to track character frequencies
✓ Want O(n) time complexity

Key Techniques:
→ Variable-size sliding window
→ Frequency array for character counting
→ Track maxFrequency (historical max)
→ Valid condition: windowLen - maxFreq <= k
→ Shrink when condition violated
→ NEVER recalculate maxFreq (use historical)

Formula:
Valid window: (right - left + 1) - maxFreq <= k

Intuition:
"With k replacements, can we make all chars same?"
Replace minority chars to majority char

Historical maxFreq Optimization:
"Only windows with higher maxFreq can beat our best"

Related Problems:
- Longest Substring with At Most K Distinct Characters (LC 340)
- Max Consecutive Ones III (LC 1004)
- Minimum Window Substring (LC 76)

🧠 Interview Strategy

Step 1: "Need longest substring with at most k replacements"
Step 2: "Use sliding window with frequency tracking"
Step 3: "Valid if (windowLen - maxFreq) <= k"
Step 4: "Expand always, shrink when invalid"
Step 5: "Use HISTORICAL maxFreq - brilliant optimization!"
Step 6: "O(n) time, O(1) space"

Key Points to Mention:
- Variable-size sliding window
- Frequency array for counting
- Valid condition: replacements needed ≤ k
- Track historical maxFreq (don't recalculate!)
- Explain why historical max works:
  * Only looking for longer windows
  * Need higher maxFreq to beat current best
  * Historical max acts as filter
  * Automatically updates when we find higher freq
- Shrink while invalid
- Update maxLen when valid
- O(n) time, each char visited twice max
- O(1) space for fixed-size array (26 chars)

This optimization is interview gold! 🏆

---

📝 Quick Revision Notes

🎯 Core Concept:

Variable-size sliding window with frequency array. Valid window: windowLen - maxFreq ≤ k. Use HISTORICAL maxFreq (never recalculate - brilliant optimization!).

⚡ Quick Implementation:

  public int characterReplacement(String s, int k) {
    // s = "AABABBA", k = 1
    // [A] → length=1, maxFreq=1, replace=0 ≤ 1 ✓
    // [A A] → length=2, maxFreq=2, replace=0 ≤ 1 ✓
    // [A A B] → length=3, maxFreq=2, replace=1 ≤ 1 ✓
    // [A A B A] → length=4, maxFreq=3, replace=1 ≤ 1 ✓, max=4
    // [A A B A B] → length=5, maxFreq=3, replace=2 > 1 ✗
    // Shrink: [A B A B] → length=4, maxFreq=2, replace=2 > 1 ✗
    // Shrink: [B A B] → length=3, maxFreq=2, replace=1 ≤ 1 ✓
    // [B A B B] → length=4, maxFreq=3, replace=1 ≤ 1 ✓, max=4
    // [B A B B A] → length=5, maxFreq=3, replace=2 > 1 ✗
    // Maximum length: 4

    int res = Integer.MIN_VALUE;
    int maxFreq = Integer.MIN_VALUE;
    int len = s.length();
    int left = 0;
    int right = 0;
    HashMap<Character, Integer> map = new HashMap<>();

    while (right < len) {
      char ch = s.charAt(right);

      // Update map and update maxFreq
      map.put(ch, map.getOrDefault(ch, 0) + 1);
      maxFreq = Math.max(maxFreq, map.get(ch));

      int currWindowLen = right - left + 1;
      // Means there are less than k chars which are to be replaced. Update res.
      if (currWindowLen - maxFreq <= k) {
        res = Math.max(res, currWindowLen);
      } else {
        // keep on shrinking the window on left side
        // update maxFreq and also res
        while (left <= right && currWindowLen - maxFreq > k) {
          char shrinkedChar = s.charAt(left);
          map.put(shrinkedChar, map.get(shrinkedChar) - 1);
          // Below is BEST optimization done though its very confusing and tricky.
          // Otherwise also, solution gets SUBMITTED.
          // https://www.youtube.com/watch?v=_eNhaDCr6P0 => check video from 21:00
          // maxFreq = Collections.max(map.values());
          left++;

          currWindowLen = right - left + 1;
          if (currWindowLen - maxFreq <= k) {
            res = Math.max(res, currWindowLen);
          }
        }
      }

      right++;
    }

    return res;
  }

🔑 Key Insights:

• Valid condition: windowLen - maxFreq <= k
• maxFreq: Most frequent character count
• HISTORICAL maxFreq: Only increases, never decreases
• Why no recalculation works:
• We're finding LONGEST substring
• Need higher maxFreq to beat current best
• Historical max acts as filter
• Math proof: need maxFreq ≥ (old + 1) to beat old length
• Automatically updates when we find higher frequency
• Frequency array: count[s.charAt(i) - 'A'] for uppercase
• Expand: Always add right character
• Shrink: While windowLen - maxFreq > k
• Update maxLen: After shrinking (when valid)
• Time: O(n) - each char visited at most twice
• Space: O(1) - array size 26 (constant)

🎪 Memory Aid:

"Length MINUS maxFreq = replacements! Valid if ≤ k! Historical max = FILTER!"
Think: "Keep historical max, only BETTER windows can beat it!"

💎 Why Historical maxFreq is Genius:

Found: length 4 with maxFreq = 3

To beat this:
- Need length > 4
- Which needs maxFreq > 3
- Historical max = 3 filters out worse windows
- Only when actual freq > 3, we progress!

It's lazy evaluation - only update when absolutely necessary!

---

Related Patterns

• Longest Substring with At Most K Distinct Characters (LC 340)
• Max Consecutive Ones III (LC 1004)
• Minimum Window Substring (LC 76)
• Longest Substring Without Repeating Characters (LC 3)

---

Happy practicing! 🎯

---

🚫 Approach 1 — Brute Force

Thought Process

[Think like a layman on steps how you will solve this problem]

Algorithm / Pseudocode

[Provide high level steps so that I can code]

Code

// Add your Java code here

Time & Space Complexity

[Add complexity analysis]

---

✅ Approach 2 — Optimal

Thought Process

[How did you arrive at the optimal solution]

Algorithm / Pseudocode

[Provide high level steps so that I can code]

Code

// Add your optimal Java code here

Time & Space Complexity

[Add complexity analysis]

---

🔄 Weekly Quick Revision

[Add a summary to revise the mental model and optimal concept quickly]