What is the time and space complexity of Longest Repeating Character Replacement?

Time complexity: O(n). Space complexity: O(1).

Longest Repeating Character Replacement

Med

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Longest Repeating Character Replacement

Approach

Track character frequencies in the current window and the maximum frequency of any single character. The window is valid when (window size - max frequency) <= k, meaning the non-majority characters can all be replaced within k operations. When invalid, shrink from the left by one.

Complexity Analysis

Time: O(n)
Space: O(1)

Pattern

Sliding Window (Variable Size)

Why It Works

The key insight is that we never need to decrease maxFreq when shrinking. Even if maxFreq is stale, a window can only grow larger if a truly higher frequency is found. This means the window size only increases when we find a better answer, giving us the correct maximum.

Updated Feb 2026