Is Longest Repeating Character Replacement easy or hard?

The problem is classified as Medium on LeetCode. The difficulty comes from recognizing the sliding window invariant: the window stays valid while replacements needed are at most k. Once that condition is clear, the implementation becomes straightforward.

Longest Repeating Character Replacement Python/Java solution

Most implementations use a sliding window with a 26-length frequency array. Python typically uses a list for counts, while Java and C++ use integer arrays. The algorithm expands the right pointer, updates counts, and shrinks the window whenever more than k replacements are needed.

How to solve Longest Repeating Character Replacement in O(n)?

Use a sliding window with two pointers. Track character counts inside the window and maintain the maximum frequency of any character. If (window size − max frequency) becomes greater than k, move the left pointer to shrink the window. Continue expanding the right pointer and update the maximum valid window length.

What is the best approach for Longest Repeating Character Replacement?

The optimal approach is a sliding window with a frequency count of characters. Maintain a window and track the most frequent character inside it. The window is valid if (window length − max frequency) ≤ k. This method runs in O(n) time and O(1) space because the alphabet size is fixed.

Is Longest Repeating Character Replacement asked at Google/Amazon/Meta?

Longest Repeating Character Replacement is a common sliding window interview problem reported in interviews at companies like Amazon, Google, Meta, and Microsoft. It tests understanding of two‑pointer techniques, frequency counting, and maintaining window constraints efficiently.

What data structure is used in Longest Repeating Character Replacement?

A frequency array or hash table is used to store counts of characters inside the current window. Because the string contains only uppercase English letters, a fixed array of size 26 is typically used, providing constant-time updates and lookups.

What is the time complexity of Longest Repeating Character Replacement?

The optimal sliding window solution runs in O(n) time where n is the length of the string. Each character is added to and removed from the window at most once. Space complexity is O(1) since only a fixed array of size 26 is required for character frequencies.

Description Solution Video 20:44

424. Longest Repeating Character Replacement

Medium60.4% acceptance22 companies

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:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: 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: