LeetCode 424: Longest Repeating Character Replacement Solution in Python – A Step-by-Step Guide

What Is LeetCode 424: Longest Repeating Character Replacement?

In LeetCode 424: Longest Repeating Character Replacement, you’re given a string s (e.g., "AABABBA") and an integer k, representing the maximum number of character replacements allowed. Your task is to return the length of the longest substring that can be made into all the same character by replacing up to k letters. For example, with "AABABBA" and k = 1, you can replace one 'B' to get "AAAAABA" (length 6) or tweak elsewhere, but 6 is the max. The string uses only uppercase letters, and you’re optimizing for the longest uniform stretch.

Problem Statement

• Input: A string s, an integer k.
• Output: An integer—the length of the longest substring achievable with ≤ k replacements.
• Rules:
• Replace any character with any uppercase letter.
• Maximize length of a substring with all same characters.
• Use up to k replacements.

Constraints

• 1 <= s.length <= 10⁵.
• s consists of only uppercase English letters.
• 0 <= k <= s.length.

Examples

• Input: s = "ABAB", k = 2
• Output: 4 (replace 'B's to "AAAA").
• Input: s = "AABABBA", k = 1
• Output: 4 (e.g., "AAAA" by replacing one 'B').
• Input: s = "AAAA", k = 2
• Output: 4 (already all 'A', no replacements needed).

Understanding the Problem: Stretching the String

To solve LeetCode 424: Longest Repeating Character Replacement in Python, we need to find the longest substring that can become all one character with up to k replacements. A naive idea might be to try replacing every possible set of k characters—but with up to 10⁵ length, that’s combinatorially explosive! Instead, we’ll use:

• Best Solution (Sliding Window with Frequency Tracking): O(n) time, O(1) space—optimizes with a window.
• Alternative Solution (Brute Force Simulation): O(n * k * 26) time, O(1) space—tries all tweaks.

Let’s dive into the sliding window solution with a clear, step-by-step explanation.

Best Solution: Sliding Window with Frequency Tracking

Why This Is the Best Solution

The sliding window with frequency tracking method is the top pick because it’s fast—O(n) time, O(1) space (26 letters)—and cleverly uses a sliding window to maximize the stretch without over-replacing. It tracks the most frequent character in the window and ensures the number of replacements (window size minus max frequency) stays within k, sliding the window as needed. It’s like stretching a rubber band over the string, adjusting it to fit the longest uniform piece with k fixes!

How It Works

Think of the string as a stretchy tape you’re shaping:

• Step 1: Set Up Window:
• Use two pointers: left (start), right (end).
• Track frequency of each letter in a count array.
• Step 2: Expand and Shrink:
• Move right, add new char to count.
• window_len = right - left + 1.
• max_count: Most frequent char in window.
• If window_len - max_count > k (too many replacements), shrink by moving left.
• Step 3: Track Max Length:
• Update max length as window grows.
• Step 4: Why This Works:
• Window size - max frequency = replacements needed.
• Sliding keeps it within k, maximizing length.
• It’s like finding the widest net you can cast with k patches!

Step-by-Step Example

Example: s = "AABABBA", k = 1

• Setup: left = 0, right = 0, count = [0]*26, max_len = 0.
• r=0: "A", count[A]=1, max_count=1, len=1, 1-1=0 ≤ 1, max_len=1.
• r=1: "AA", count[A]=2, max_count=2, len=2, 2-2=0 ≤ 1, max_len=2.
• r=2: "AAB", count[A]=2, B=1, max_count=2, len=3, 3-2=1 ≤ 1, max_len=3.
• r=3: "AABA", count[A]=3, B=1, max_count=3, len=4, 4-3=1 ≤ 1, max_len=4.
• r=4: "AABAB", count[A]=3, B=2, max_count=3, len=5, 5-3=2 > 1, shrink:
• l=1: "ABAB", A=2, B=2, len=4, 4-2=2 > 1.
• l=2: "BAB", A=1, B=2, len=3, 3-2=1 ≤ 1, max_len=4.
• r=5: "BABB", A=1, B=3, len=4, 4-3=1 ≤ 1, max_len=4.
• r=6: "BABBA", A=2, B=3, len=5, 5-3=2 > 1, l=3: "ABBA", A=2, B=2, len=4, 4-2=2 > 1, l=4: "BBA", A=1, B=2, len=3, 3-2=1 ≤ 1, max_len=4.
• Result: 4.

Example: s = "ABAB", k = 2

• r=0 to 3: "ABAB", A=2, B=2, len=4, 4-2=2 ≤ 2, max_len=4.
• Result: 4.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy codeclass Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        # Step 1: Initialize window
        count = [0] * 26  # Frequency of A-Z
        left = 0
        max_len = 0
        max_count = 0  # Most frequent char count

        # Step 2: Slide window
        for right in range(len(s)):
            # Add right char
            char_idx = ord(s[right]) - ord('A')
            count[char_idx] += 1
            max_count = max(max_count, count[char_idx])

            # Check if window needs shrinking
            window_len = right - left + 1
            if window_len - max_count > k:
                count[ord(s[left]) - ord('A')] -= 1
                left += 1
                # Recalculate max_count not needed (optimization)

            max_len = max(max_len, right - left + 1)

        return max_len

• Line 4-8: Setup:
• count: Array for A-Z frequencies.
• left: Window start (0).
• max_len: Longest valid stretch.
• max_count: Max frequency in window.
• Line 11-22: Slide window:
• Line 12-14: Add s[right] to count, update max_count.
• Line 16-20: Check window:
• window_len: Current size.
• If window_len - max_count > k, shrink by moving left, reduce count.
• Note: Not updating max_count after shrink is an optimization (max still holds).
• Line 21: Update max_len.
• Line 23: Return longest stretch.
• Time Complexity: O(n)—one pass, 26 letters constant.
• Space Complexity: O(1)—fixed 26-size array.

This is like stretching a string with a sliding fix-it window!

Alternative Solution: Brute Force Simulation

Why an Alternative Approach?

The brute force simulation method tries all starting points and replaces up to k characters to maximize a repeating stretch, checking each possibility. It’s O(n * k * 26) time and O(1) space—intuitive but slow for large inputs. It’s like testing every tweak spot to see how far you can stretch!

How It Works

Picture it as tweaking the string:

• Step 1: For each start position.
• Step 2: Try replacing up to k chars with each letter (A-Z).
• Step 3: Find max stretch of same char.

Step-by-Step Example

Example: s = "AABABBA", k = 1

• Start 0: "AABABBA":
• Replace B at 2 with A: "AAAABBA", stretch = 4.
• Max = 4.
• Start 1: "ABABBA":
• Replace B at 1 with A: "AAABBA", stretch = 4.
• Max = 4.
• Continue: Check all, max stretch = 4.
• Result: 4.

Code for Brute Force Approach (Simplified)

Copy codeclass Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        n = len(s)
        max_len = 0

        for start in range(n):
            for target in range(ord('A'), ord('Z') + 1):
                target = chr(target)
                changes = k
                length = 0
                for i in range(start, n):
                    if s[i] == target:
                        length += 1
                    elif changes > 0:
                        changes -= 1
                        length += 1
                    else:
                        break
                    max_len = max(max_len, length)

        return max_len

• Time Complexity: O(n * k * 26)—n starts, k changes, 26 letters.
• Space Complexity: O(1)—few variables.

It’s a slow stretch-tester!

Comparing the Two Solutions

• Sliding Window (Best):
• Pros: O(n), O(1), fast and sleek.
• Cons: Window logic to grasp.
• Brute Force (Alternative):
• Pros: O(n * k * 26), O(1), intuitive.
• Cons: Too slow.

Sliding window wins for speed.

Additional Examples and Edge Cases

• "A", 0: 1.
• "AB", 1: 2.
• "AAA", 0: 3.

Sliding window handles all.

Complexity Breakdown

• Sliding Window: Time O(n), Space O(1).
• Brute Force: Time O(n * k * 26), Space O(1).

Sliding’s the champ.

Key Takeaways

• Sliding Window: Stretch smart!
• Brute Force: Try it all!
• Replacements: Windows rule.
• Python Tip: Counts rock—see [Python Basics](/python/basics).

Final Thoughts: Stretch That String

LeetCode 424: Longest Repeating Character Replacement in Python is a string-stretching adventure. Sliding window with frequency tracking zips to the max, while brute force trudges through tweaks. Want more string fun? Try LeetCode 3: Longest Substring Without Repeating Characters or LeetCode 76: Minimum Window Substring. Ready to stretch? Head to Solve LeetCode 424 on LeetCode and max that stretch today!