Use a sliding window with a frequency map. A window is valid if you can make all characters the same with at most k replacements.
The number of replacements needed is windowSize - maxFreq, where maxFreq is the count of the most frequent character. If this exceeds k, shrink the window from the left.
The trick: you don't need to recompute maxFreq when shrinking. You can keep track of the historical maximum. Even if the true max frequency drops, your answer can only come from windows where maxFreq was at least as large.
With s = "AABABBA" and k = 1: window "AABA" has maxFreq = 3 (for 'A'). Size is 4. Replacements needed: 4 - 3 = 1 \le k. Valid.