Longest-repeating-character-replacement https://leetcode.com/problems/longest-repeating-character-replacement/submissions/

CharacterReplacement.java

class Solution {
    public int characterReplacement(String s, int k) {
        int windowStart = 0;
        int[] frequenciesInCurrentWindow = new int['A' + 26];
        int maxFrequencyOfDominantCharacterSoFar = 0;
        int kMinus1 = k - 1;
        for (int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
            char rightChar = s.charAt(windowEnd);
            int rightCharFrequency = ++frequenciesInCurrentWindow[rightChar];

            // You have to think about the following loop this way:
            //
            // Current window is denoted by `frequenciesInCurrentWindow` array which keeps track how many times
            // various characters occur in the current window.
            //
            // Every iteration we will keep a running `maxFrequencyOfDominantCharacterSoFar` variable.
            //
            // Logically you can think of it as:
            // `maxFrequencyOfDominantCharacterSoFar = Math.max(frequenciesInCurrentWindow)`
            // which is being updated every iteration.
            //
            // We iterate a sliding window. Every iteration a new character `rightChar` gets into the current window
            // The new character might be:
            // 1) the same dominant character as in the current window, thus `maxFrequencyOfDominantCharacterSoFar` must be updated
            //    this option means that we found a new answer to our problem
            // 2) or non-dominant character
            //    2.1) If current window is longer than our already found answer `maxFrequencyOfDominantCharacterSoFar + k`
            //    then the window is, in fact, too long, and we need to shrink it by 1.
            //
            //    By shrinking the window we make induction step from problem of size `N -> N-1`
            //
            //    2.2) Otherwise, do nothing
            //
            // This algorithm makes sure that we don't look up windows of `0..K-1` sizes when
            // we have already found an answer of size `K` at some point of time

            if (rightCharFrequency > maxFrequencyOfDominantCharacterSoFar) {
                maxFrequencyOfDominantCharacterSoFar = rightCharFrequency; // happy path, we have just added another dominant character to the window
            } else if (windowEnd - windowStart > kMinus1 + maxFrequencyOfDominantCharacterSoFar) { // is length of the current window > maximum length of already found window so far (maxFrequencyOfDominantCharacterSoFar + k)?
                // We added a character that bloated our window too much.
                // Now window is [dominantChar*maxFrequencyOfDominantCharacterSoFar + (k+1)*non-dominant-chars].
                // For example ...[AAAAXYZ]...
                // There is no point in:
                // 1) Adding more characters from the right and keeping the current `windowStart` pointer.
                //    Number of non-dominant-chars is already `k+1` and will only increase.
                //    Solution for the problem cannot start with current `windowStart` anymore.
                //    Example:
                //    ...[AAAAXYZ]AQWXZXXXXXXX...
                //                ^^^^^^^^^^^^
                //        these chars don't matter anymore for the current `windowStart`. They won't contribute to find an answer.
                // 2) Shrinking by more than 1 character because we would like to slide our window of size _only_ bigger or equal to `maxFrequencyOfDominantCharacterSoFar + k`
                //    there is no need to shrink window more because then we will iterate through answers that will be smaller than the already found maximum window so far (maxFrequencyOfDominantCharacterSoFar + k)
                //
                // 3) Updating `maxFrequencyOfDominantCharacterSoFar` after shrinking because:
                //    as the name of the variable implies, it is our _already_ found solution for the problem
                //    it cannot suddenly become less than it was before
                char leftChar = s.charAt(windowStart++);
                frequenciesInCurrentWindow[leftChar]--;
            }
        }
        return Math.min(maxFrequencyOfDominantCharacterSoFar + k, s.length());
    }
}

Runtime: 4 ms, faster than 97.80% of Java online submissions for Longest Repeating Character Replacement.
Memory Usage: 43.3 MB, less than 19.83% of Java online submissions for Longest Repeating Character Replacement.

When there is no Math.max, it becomes clear what really is going on when we update a running maxFrequencyOfDominantCharacterSoFar