LeetCode 424 Longest Repeating Character Replacement - Example and Complexity Analysis

Trace s = "ABAB" with k = 2.

Initialize: left = 0, maxLen = 0, maxFreq = 0, count = {}.

right = 0: Add 'A'. count = {A: 1}. maxFreq = 1. Window size 1. Replacements = 1 - 1 = 0 \le 2. Valid. maxLen = 1.

right = 1: Add 'B'. count = {A: 1, B: 1}. maxFreq = 1. Size 2. Replacements = 2 - 1 = 1 \le 2. Valid. maxLen = 2.

right = 2: Add 'A'. count = {A: 2, B: 1}. maxFreq = 2. Size 3. Replacements = 3 - 2 = 1 \le 2. Valid. maxLen = 3.

right = 3: Add 'B'. count = {A: 2, B: 2}. maxFreq = 2. Size 4. Replacements = 4 - 2 = 2 \le 2. Valid. maxLen = 4.

Return 4. The entire string can be made uniform with $2$ replacements.

Each character processed once. $O(n)$ time. Frequency map has at most $26$ entries. $O(1)$ space.