Approach Summary
Track the count of the most frequent character in the window. If window_size - max_count > k, shrink the window from the left.
Practice Mode
3 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Sliding Window with Frequency Map & Replacement Check (Optimal) | O(n) | O(1) [at most 26 entries] | Expand right pointer while tracking maxCount; shrink left pointer when window length - maxCount > k. |
| 2 Approach 2: Naive All-Substrings Frequency Scan (Baseline) | O(n²) | O(1) | Checks every substring O(n²), counting character frequencies to verify if replacements needed <= k. |
| 3 Approach 2: Naive All-Substrings Frequency Scan (Baseline) | O(n²) | O(1) | Checks every substring O(n²), counting character frequencies to verify if replacements needed <= k. |
Step 1: Baseline
Approach 1: Sliding Window with Frequency Map & Replacement Check (Optimal)
Time: O(n)
Space: O(1) [at most 26 entries]
For a window from i to j, the minimum replacements to turn the window into identical characters is (j - i + 1) - maxCount, where maxCount is the count of the most frequent character in the current window. If this value exceeds k, the window is invalid, so decrement map[s[i]] and shift i right. Otherwise, update maxLen = max(maxLen, j - i + 1).
Approach 1: Sliding Window with Frequency Map & Replacement Check (Optimal) Implementation
Approach 1: Sliding Window with Frequency Map & Replacement Check (Optimal)
class Solution {
public int characterReplacement(String s, int k) {
int maxLen = 0, maxCount = 0, i = 0, n = s.length();
Map<Character, Integer> map = new HashMap<>();
for (int j = 0; j < n; j++) {
map.put(s.charAt(j), map.getOrDefault(s.charAt(j), 0) + 1);
maxCount = Math.max(maxCount, map.get(s.charAt(j)));
if (((j - i + 1) - maxCount) > k) {
map.put(s.charAt(i), map.get(s.charAt(i)) - 1);
i++;
}
maxLen = Math.max(maxLen, j - i + 1);
}
return maxLen;
}
}class Solution {
public:
int characterReplacement(string s, int k) {
int maxLen = 0, maxCount = 0, n = s.size(), i = 0;
unordered_map<char, int> map;
for (int j = 0; j < n; j++) {
map[s[j]]++;
maxCount = max(maxCount, map[s[j]]);
if (((j - i + 1) - maxCount) > k) {
map[s[i]]--;
i++;
}
maxLen = max(maxLen, j - i + 1);
}
return maxLen;
}
};class Solution:
def characterReplacement(self, s: str, k: int) -> int:
count = {}
max_count = 0
left = 0
max_len = 0
for right in range(len(s)):
count[s[right]] = count.get(s[right], 0) + 1
max_count = max(max_count, count[s[right]])
if (right - left + 1) - max_count > k:
count[s[left]] -= 1
left += 1
max_len = max(max_len, right - left + 1)
return max_lenfunction characterReplacement(s, k) {
const map = new Map();
let maxCount = 0, maxLen = 0, i = 0;
for (let j = 0; j < s.length; j++) {
map.set(s[j], (map.get(s[j]) || 0) + 1);
maxCount = Math.max(maxCount, map.get(s[j]));
if ((j - i + 1) - maxCount > k) {
map.set(s[i], map.get(s[i]) - 1);
i++;
}
maxLen = Math.max(maxLen, j - i + 1);
}
return maxLen;
} Step 2
Approach 2: Naive All-Substrings Frequency Scan (Baseline)
Time: O(n²)
Space: O(1)
For each starting position i and ending position j, compute the frequency of all 26 uppercase letters. The number of replacements needed to convert all characters in s[i..j] into the most frequent character is (j - i + 1) - max_freq. If this value <= k, record the length j - i + 1.
Approach 2: Naive All-Substrings Frequency Scan (Baseline) Implementation
Approach 2: Naive All-Substrings Frequency Scan (Baseline)
class Solution {
public int characterReplacement(String s, int k) {
int maxLen = 0;
for (int i = 0; i < s.length(); i++) {
int[] counts = new int[26];
int maxF = 0;
for (int j = i; j < s.length(); j++) {
counts[s.charAt(j) - 'A']++;
maxF = Math.max(maxF, counts[s.charAt(j) - 'A']);
if ((j - i + 1) - maxF <= k) {
maxLen = Math.max(maxLen, j - i + 1);
}
}
}
return maxLen;
}
}class Solution {
public:
int characterReplacement(string s, int k) {
int maxLen = 0;
for (int i = 0; i < s.size(); i++) {
vector<int> counts(26, 0);
int maxF = 0;
for (int j = i; j < s.size(); j++) {
counts[s[j] - 'A']++;
maxF = max(maxF, counts[s[j] - 'A']);
if ((j - i + 1) - maxF <= k) {
maxLen = max(maxLen, j - i + 1);
}
}
}
return maxLen;
}
};class Solution:
def characterReplacement(self, s: str, k: int) -> int:
n = len(s)
max_len = 0
for i in range(n):
counts = [0] * 26
max_f = 0
for j in range(i, n):
idx = ord(s[j]) - ord('A')
counts[idx] += 1
max_f = max(max_f, counts[idx])
if (j - i + 1) - max_f <= k:
max_len = max(max_len, j - i + 1)
return max_lenfunction characterReplacement(s, k) {
let maxLen = 0;
for (let i = 0; i < s.length; i++) {
const counts = new Array(26).fill(0);
let maxF = 0;
for (let j = i; j < s.length; j++) {
const idx = s.charCodeAt(j) - 65;
counts[idx]++;
maxF = Math.max(maxF, counts[idx]);
if ((j - i + 1) - maxF <= k) {
maxLen = Math.max(maxLen, j - i + 1);
}
}
}
return maxLen;
} Step 2: Most Optimized
Approach 2: Naive All-Substrings Frequency Scan (Baseline)
Time: O(n²)
Space: O(1)
For each starting position i and ending position j, compute the frequency of all 26 uppercase letters. The number of replacements needed to convert all characters in s[i..j] into the most frequent character is (j - i + 1) - max_freq. If this value <= k, record the length j - i + 1.
Approach 2: Naive All-Substrings Frequency Scan (Baseline) Implementation
Approach 2: Naive All-Substrings Frequency Scan (Baseline)
class Solution {
public int characterReplacement(String s, int k) {
int maxLen = 0;
for (int i = 0; i < s.length(); i++) {
int[] counts = new int[26];
int maxF = 0;
for (int j = i; j < s.length(); j++) {
counts[s.charAt(j) - 'A']++;
maxF = Math.max(maxF, counts[s.charAt(j) - 'A']);
if ((j - i + 1) - maxF <= k) {
maxLen = Math.max(maxLen, j - i + 1);
}
}
}
return maxLen;
}
}class Solution {
public:
int characterReplacement(string s, int k) {
int maxLen = 0;
for (int i = 0; i < s.size(); i++) {
vector<int> counts(26, 0);
int maxF = 0;
for (int j = i; j < s.size(); j++) {
counts[s[j] - 'A']++;
maxF = max(maxF, counts[s[j] - 'A']);
if ((j - i + 1) - maxF <= k) {
maxLen = max(maxLen, j - i + 1);
}
}
}
return maxLen;
}
};class Solution:
def characterReplacement(self, s: str, k: int) -> int:
n = len(s)
max_len = 0
for i in range(n):
counts = [0] * 26
max_f = 0
for j in range(i, n):
idx = ord(s[j]) - ord('A')
counts[idx] += 1
max_f = max(max_f, counts[idx])
if (j - i + 1) - max_f <= k:
max_len = max(max_len, j - i + 1)
return max_lenfunction characterReplacement(s, k) {
let maxLen = 0;
for (let i = 0; i < s.length; i++) {
const counts = new Array(26).fill(0);
let maxF = 0;
for (let j = i; j < s.length; j++) {
const idx = s.charCodeAt(j) - 65;
counts[idx]++;
maxF = Math.max(maxF, counts[idx]);
if ((j - i + 1) - maxF <= k) {
maxLen = Math.max(maxLen, j - i + 1);
}
}
}
return maxLen;
}Edge Cases to Watch
- k >= len(s) (can convert whole string; returns len(s))
- All characters already identical (e.g. "AAAA", k = 2; returns 4)
- k = 0 (finds longest contiguous run of identical characters)
- Alternating characters (e.g. "ABAB", k = 2; returns 4)
Algorithmic Pattern
View Pattern Guide →
Master the Sliding Window Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Sliding Window pattern.
Framework: Sliding Window • Interview Prep: Tested at FAANG •
Explore all Sliding Window problems & invariants →
How to Recognize This Pattern
- Replace at most k characters
- Longest uniform substring
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Tags
String Sliding Window
Frequently Asked Questions
What is the optimal time and space complexity for Longest Repeating Character Replacement?
The optimal solution for Longest Repeating Character Replacement achieves O(n) runtime complexity and requires O(1) auxiliary space. Time complexity is O(n) because each pointer left and right traverses the string at most once. Space complexity is O(1) (or O(26)) since only frequencies of uppercase English letters are stored.
How do I identify that Longest Repeating Character Replacement requires the Sliding Window pattern?
In technical interviews, look for key problem signals: Replace at most k characters; Longest uniform substring. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Sliding Window strategy.
What critical edge cases must be handled in Longest Repeating Character Replacement?
Essential edge cases to verify include: k >= len(s) (can convert whole string; returns len(s)); All characters already identical (e.g. "AAAA", k = 2; returns 4); k = 0 (finds longest contiguous run of identical characters); Alternating characters (e.g. "ABAB", k = 2; returns 4). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Longest Repeating Character Replacement?
Longest Repeating Character Replacement is a Medium-difficulty question tagged with medium recurrence. It is actively asked in technical screening and onsite interview loops at Google, Amazon.