Log inSign up
mediumleetcodeNot Started

Longest Repeating Character Replacement

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

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 · Example:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two As with two Bs or vice versa to get "BBBB" or "AAAA" of length 4.

Example 2 · Example:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the middle A with B to form "AABBBBA" containing "BBBB" of length 4.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate window validity condition: length - maxFreq <= k.
  • Understand the non-shrinking sliding window property.
  • Maintain frequency tracking with constant 26-element array.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Longest substring with at most k replacements/mismatches.
  • Monotonic maximum window size tracking.

Algorithmic Decision Tree:

  • Dynamic Sliding Window
  • Non-Shrinking Window Invariant

Connected Patterns:

Max Consecutive Ones IIIMinimum Window SubstringLongest Substring Without Repeating Characters

1. All Substrings Frequency Evaluation

Intuition

For each start index i from 0 to N - 1: maintain a 26-count array. For each end index j from i to N - 1: increment count of s[j], find maxFreq among all 26 counts. If (j - i + 1) - maxFreq <= k, update maxLen = max(maxLen, j - i + 1).

When to apply: Basic baseline comparison.

Algorithm

  1. Initialize maxLen = 0.
  2. For i from 0 to n - 1:
  3. count = [0] * 26, maxFreq = 0.
  4. For j from i to n - 1:
  5. count[s[j] - 'A']++.
  6. maxFreq = max(maxFreq, count[s[j] - 'A']).
  7. If (j - i + 1) - maxFreq <= k: maxLen = max(maxLen, j - i + 1).
  8. Return maxLen.

All Substrings Frequency Evaluation

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [A, A, B, A, B, B, A]
Current operationSTEP 1 OF 6
Observation: Inspect candidate window s[0
Visual state
Values and pointers at this exact step
array
S
A
A
B
A
B
B
A
0
↑ i=0
1
2
↑ j=2 ('AAB')
3
4
5
6
Variables at this step
i
0
j
2
window
AAB
counts
{"A":2,"B":1}
maxFreq
2
valid
true
maxLen
3
Check / comparison
Window s[0..2] = 'AAB'. Counts: {A: 2, B: 1}. maxFreq = 2.
Decision / next transition
Replacements = len (3) - maxFreq (2) = 1 <= k (1). Valid! maxLen = 3.
Why this step matters

Observation: Inspect candidate window s[0..2] = 'AAB' of length 3.

Decision: Dominant character is 'A' with count 2. Replacements needed = 3 - 2 = 1 <= k (1). Valid window; update maxLen = 3.

Invariant: A substring can be transformed into repeating characters if len - maxFreq <= k.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7public:
8 int characterReplacement(std::string s, int k) {
9 int n = s.size(), maxLen = 0;
10 for (int i = 0; i < n; ++i) {
11 int count[26] = {0};
12 int maxFreq = 0;
13 for (int j = i; j < n; ++j) {
14 count[s[j] - 'A']++;
15 maxFreq = std::max(maxFreq, count[s[j] - 'A']);
16 if ((j - i + 1) - maxFreq <= k) {
17 maxLen = std::max(maxLen, j - i + 1);
18 }
19 }
20 }
21 return maxLen;
22 }
23};
24
25int main() {
26 Solution sol;
27 std::cout << sol.characterReplacement("ABAB", 2) << std::endl; // 4
28 std::cout << sol.characterReplacement("AABABBA", 1) << std::endl; // 4
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(N^2) — N2 substrings evaluated in constant operations.
  • Space complexity: O(1)

Why Brute Force Doesn't Scale:

Non-shrinking window in strict single-pass O(N).

26-integer stack array.

2. Shrinking Sliding Window

Intuition

Maintain left = 0, count[26]. For right from 0 to N - 1: increment count[s[right]], update maxFreq. While (right - left + 1) - maxFreq > k: decrement count[s[left]] and advance left++. Update maxLen = max(maxLen, right - left + 1).

When to apply: Standard shrinking sliding window approach.

Algorithm

  1. Initialize count[26] = 0, left = 0, maxFreq = 0, maxLen = 0.
  2. For right from 0 to n - 1:
  3. count[s[right] - 'A']++.
  4. maxFreq = max(maxFreq, count[s[right] - 'A']).
  5. While (right - left + 1) - maxFreq > k:
  6. count[s[left] - 'A']--.
  7. left++.
  8. maxLen = max(maxLen, right - left + 1).
  9. Return maxLen.

Shrinking Sliding Window

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [A, A, B, A, B, B, A]
Current operationSTEP 1 OF 6
Observation: Start window at index 0
Visual state
Values and pointers at this exact step
array
S
A
A
B
A
B
B
A
0
↑ L=0, R=0 ('A')
1
2
3
4
5
6
Variables at this step
L
0
R
0
counts
{"A":1}
maxFreq
1
maxLen
1
Check / comparison
Window [0..0]: counts {A: 1}, maxFreq = 1. len = 1.
Decision / next transition
len - maxFreq = 1 - 1 = 0 <= 1. Valid; maxLen = 1.
Why this step matters

Observation: Start window at index 0. Count of 'A' is 1, maxFreq = 1.

Decision: 1 - 1 = 0 <= k (1). Valid window; advance R to 1.

Invariant: Window maintains current counts and dynamically tracks peak frequency.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <algorithm>
4
5class Solution {
6public:
7 int characterReplacement(std::string s, int k) {
8 int count[26] = {0};
9 int left = 0, maxFreq = 0, maxLen = 0;
10
11 for (int right = 0; right < (int)s.size(); ++right) {
12 count[s[right] - 'A']++;
13 maxFreq = std::max(maxFreq, count[s[right] - 'A']);
14
15 while ((right - left + 1) - maxFreq > k) {
16 count[s[left] - 'A']--;
17 left++;
18 }
19 maxLen = std::max(maxLen, right - left + 1);
20 }
21 return maxLen;
22 }
23};
24
25int main() {
26 Solution sol;
27 std::cout << sol.characterReplacement("ABAB", 2) << std::endl; // 4
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(N) — Both left and right pointers traverse at most N times.
  • Space complexity: O(1)

3. Non-Shrinking Sliding Window (Optimal O(N))

Intuition

The maximum valid window size seen so far is maxLen. If a new character expands the window to right - left + 1 such that (right - left + 1) - maxFreq > k, we only shift left forward by 1 step (if instead of while), keeping the window size fixed. The window will only grow when a larger valid size is encountered. At the end, s.length - left is exactly the maximum valid length.

When to apply: The standard gold standard solution.

Algorithm

  1. Initialize count = new int[26], left = 0, maxFreq = 0.
  2. For right from 0 to s.length - 1:
  3. count[s[right] - 'A']++.
  4. maxFreq = max(maxFreq, count[s[right] - 'A']).
  5. If (right - left + 1) - maxFreq > k:
  6. count[s[left] - 'A']--.
  7. left++.
  8. Return s.length - left.

Sliding Window with Dynamic Max Frequency Tracking

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [A, A, B, A, B, B, A]
Current operationSTEP 1 OF 7
Observation: Initialize window at [0, 0]
Visual state
Values and pointers at this exact step
array
S
A
A
B
A
B
B
A
0
↑ L=0, R=0 ('A')
1
2
3
4
5
6
Variables at this step
L
0
R
0
windowLen
1
counts
{"A":1}
maxFreq
1
replacementsNeeded
0
k
1
maxLen
1
Why this step matters

Observation: Initialize window at [0, 0]. Character 'A' has frequency 1.

Decision: windowLen (1) - maxFreq (1) = 0 <= k (1). Window is valid; update maxLen = 1.

Invariant: When replacements needed (len - maxFreq) <= k, the window can form a valid repeating sequence.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <algorithm>
4
5class Solution {
6public:
7 int characterReplacement(std::string s, int k) {
8 int count[26] = {0};
9 int left = 0, maxFreq = 0;
10
11 for (int right = 0; right < (int)s.size(); ++right) {
12 count[s[right] - 'A']++;
13 maxFreq = std::max(maxFreq, count[s[right] - 'A']);
14
15 if ((right - left + 1) - maxFreq > k) {
16 count[s[left] - 'A']--;
17 left++;
18 }
19 }
20 return s.size() - left;
21 }
22};
23
24int main() {
25 Solution sol;
26 std::cout << sol.characterReplacement("ABAB", 2) << std::endl; // 4
27 std::cout << sol.characterReplacement("AABABBA", 1) << std::endl; // 4
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(N) strictly — Exact single pass with no while loops.
  • Space complexity: O(1) (26 integers)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force All SubstringsO(N^2 * 26)O(1)Evaluates every substring.Quadratic time complexity.
2.Standard Shrinking Sliding WindowO(26 * N)O(1)Intuitive window contraction.Recalculates maxFreq across 26 characters on shrink.
3.Non-Shrinking Sliding Window (Optimal)OptimalO(N) strictlyO(1) extra spaceZero recalculation of maxFreq; runs in pure single linear pass.Requires understanding the non-shrinking window invariant.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Recalculating maxFreq over all 26 characters on every step, degrading performance to O(26 * N).

Pitfall 2:

Shrinking maxFreq when window shifts (maxFreq only needs to record the historical maximum).

Crucial Edge Cases to Validate:

  • k >= s.length: Returns s.length (can change all characters to identical letter).
  • k == 0: Returns length of longest consecutive identical character run.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the condition windowLength - maxFreq <= k clearly.
  2. Explain the non-shrinking window invariant and why s.length - left gives the optimal answer.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is it safe not to decrement maxFreq when shifting left?

Back to DSA Sheet