#424

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Longest Repeating Character Replacement

Find the length of the longest substring after at most k replacements using a sliding window and character count tracking.

hash table string sliding window

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

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

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.

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.

terminal

Solution

Solution 1: Two Pointers

We use a hash table `cnt` to count the occurrence of each character in the string, and two pointers `l` and `r` to maintain a sliding window, such that the size of the window minus the count of the most frequent character does not exceed $k$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        cnt = Counter()
        l = mx = 0
        for r, c in enumerate(s):
            cnt[c] += 1
            mx = max(mx, cnt[c])
            if r - l + 1 - mx > k:
                cnt[s[l]] -= 1
                l += 1
        return len(s) - l

Continue Practicing

#438 find all anagrams in a string #395 longest substring with at least k repeating characters #567 permutation in string