How to Solve Longest Repeating Character Replacement

This problem can be solved by maintaining a sliding window and tracking the most frequent character count. Expand the window greedily and shrink only when the replacements exceed k. The approach ensures each character is counted efficiently, achieving linear time complexity while managing the running state with a hash table.

Problem Statement

You are given a string s and an integer k. You may change any character in s to any uppercase English letter at most k times. Determine the maximum length of a substring that contains only one repeated character after performing these operations.

For example, given s = "ABAB" and k = 2, you can replace two characters to form a substring of four identical letters. Return the length of the longest possible such substring after at most k replacements. Constraints: 1 <= s.length <= 105, s consists only of uppercase English letters, 0 <= k <= s.length.

Examples

Example 1

Input: s = "ABAB", k = 2

Output: 4

Replace the two 'A's with two 'B's or vice versa.

Example 2

Input: s = "AABABBA", k = 1

Output: 4

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 <= 105
• s consists of only uppercase English letters.
• 0 <= k <= s.length

Solution Approach

Sliding Window with Character Count

Use a sliding window to expand right and track counts of characters in a hash table. Keep the count of the most frequent character and calculate the required replacements. If the window needs more than k replacements, shrink from the left.

Greedy Expansion

Always expand the window to include new characters. Only shrink when the number of characters that need replacement exceeds k. This ensures we maximize the window size at every step while tracking running state efficiently.

Tracking Maximum Length

Keep a running maximum of the window size. The maximum substring length is the largest window where the difference between window length and the count of the most frequent character is <= k. This captures the longest repeating substring achievable.

Complexity Analysis

Time complexity is O(n) because each character is processed once when expanding and possibly once when shrinking the window. Space complexity is O(1) since the hash table only tracks counts for uppercase letters, a fixed-size alphabet.

What Interviewers Usually Probe

• Pay attention to when to shrink the window; miscalculating replacements can fail the test cases.
• Tracking the most frequent character is key; using total distinct counts leads to incorrect window evaluation.
• Optimizing with a hash table prevents repeated scanning of the window, keeping linear performance.

Common Pitfalls or Variants

Common pitfalls

• Assuming all k replacements are always used; sometimes the optimal window uses fewer than k.
• Recomputing the most frequent character for every window adjustment, causing O(n^2) complexity.
• Shrinking the window incorrectly when the required replacements equal k, missing the maximum length.

Follow-up variants

• Longest substring with at most k character changes allowing lowercase letters.
• Compute longest repeating substring for binary strings with at most k flips.
• Determine the minimal k needed to make the entire string a single repeating character.

How GhostInterview Helps

• Identifies the correct sliding window boundaries and keeps track of character frequencies efficiently.
• Highlights when to shrink or expand the window to maintain valid replacement constraints.
• Provides step-by-step simulation for edge cases like alternating characters or k=0.

Topic Pages

• Hash Table
• String
• Sliding Window

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the main pattern used in Longest Repeating Character Replacement?

The main pattern is a sliding window with running state updates, tracking the most frequent character count and adjusting window size.

Can this problem be solved without a hash table?

While possible with brute-force, a hash table allows tracking character frequencies efficiently, keeping the solution linear in time.

What happens if k is zero?

The problem reduces to finding the longest contiguous substring with identical characters without any replacements.

Is the window always shrunk when replacements exceed k?

Yes, the window is shrunk from the left until the number of required replacements is <= k to maintain a valid substring.

Why track the most frequent character instead of all counts?

Tracking only the maximum frequency avoids recomputing the entire count array for each window adjustment, ensuring O(n) performance.