LeetCode 424 Longest Repeating Character Replacement - Why Naive Fails

Try all substrings. For each, count character frequencies and check if you can make all characters the same with at most k replacements.

There are $O(n^2)$ substrings. Counting frequencies for each takes $O(n)$. Total: $O(n^3)$.

For $n = 10^5$, that's $10^{15}$ operations. Far too slow.