Update Result:

Continuously update the answer (ans) using the valid window size.

Code

[{"language":"Java","code":"class Solution {\n    /**\n     * Finds the length of the longest substring by re-evaluating \n     * max frequency on each iteration.\n     */\n    public int characterReplacement(String s, int k) {\n        int[] counts = new int[26];\n        int l = 0;\n        int ans = 0;\n\n        for (int r = 0; r < s.length(); r++) {\n            // Add the new character to the window\n            counts[s.charAt(r) - 'A']++;\n\n            // Shrink the window as long as it's invalid.\n            // We re-calculate the max frequency in each check.\n            while ((r - l + 1) - max(counts) > k) {\n                counts[s.charAt(l) - 'A']--;\n                l++;\n            }\n\n            // The window is now valid, update the answer\n            ans = Math.max(ans, r - l + 1);\n        }\n\n        return ans;\n    }\n    /**\n     * Helper function to get the max frequency from the counts array.\n     */\n    private int max(int[] counts) {\n        int max_val = 0;\n        for (int count: counts) {\n            max_val = Math.max(max_val, count);\n        }\n        return max_val;\n    }\n}","lang":"java"},{"language":"Python","code":"class Solution:\n\n    def characterReplacement(self, s: str, k: int) -> int:\n        \"\"\"\n    Finds the length of the longest substring by re-evaluating \n    max frequency on each iteration.\n    \"\"\"\n        counts = [0] * 26\n        l = 0\n        ans = 0\n\n        for r in range(len(s)):\n            # Add the new character to the window\n            counts[ord(s[r]) - ord('A')] += 1\n\n            # Shrink the window as long as it's invalid.\n            # We re-calculate max(counts) in each check.\n            while (r - l + 1) - max(counts) > k:\n                counts[ord(s[l]) - ord('A')] -= 1\n                l += 1\n\n            # The window is now valid, update the answer\n            ans = max(ans, r - l + 1)\n\n        return ans","lang":"python"}]

Complexity

⏰ Time complexity: O(26 * n) = O(n) for iterating through the string + O(26) for recalculating the max frequency at each step. Though linear in nature, recalculation adds overhead, making this approach slightly less efficient for long strings.
🧺 Space complexity: O(1) for the frequency array (fixed size counts[26]).

Method 2 - Sliding Window without max frequency recalculation

Intuition

Instead of recalculating the max frequency from the frequency map on every iteration, maintain a running value (maxCharCount) that tracks the highest frequency character seen within the current sliding window. This approach avoids frequent scanning of the frequency map, making it more efficient when dealing with large strings.

Approach

Track Character Frequencies:
- Use a frequency HashMap to dynamically count characters in the current window.
- Maintain a variable maxCharCount to store the highest frequency of any single character in the window.
Expand Window:
- For each new character added (s[r]), update its frequency in the map and update maxCharCount if the frequency of the current character becomes higher.
Check Validity:
- Calculate the number of changes (window size - maxCharCount).
- If this exceeds k, shrink the window by decrementing the frequency of s[l] and adjusting the l pointer.
Update Result:
- Continuously update the answer (ans) using the valid window size.

Related Tags