LeetCode 424: Longest Repeating Character Replacement Solution

Master LeetCode problem 424 (Longest Repeating Character Replacement), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

424. Longest Repeating Character Replacement

Medium

Hash Table String Sliding Window

Problem Explanation

Explanation:

To solve this problem, we can use a sliding window approach. We will maintain a window that contains the longest substring with the same character. We will try to extend this window by allowing at most k replacements.

Initialize variables maxLen to store the maximum length of the substring with the same character, maxCount to store the count of the most frequent character in the current window, and start to mark the start of the window.
Iterate over the string using two pointers, end and start, to represent the end and start of the current window.
Calculate the length of the current window by end - start + 1. If the length minus the maximum count of characters in the window is greater than k, we need to shrink the window.
Update maxLen if the current window length is greater.
Move the start pointer to shrink the window by decrementing the count of the character at start.
Update maxCount when we encounter a character with a higher frequency.
Repeat steps 3-6 until the end of the string.
Return maxLen as the result.

Time Complexity: O(n) where n is the length of the input string. Space Complexity: O(1)

Solution Code

class Solution {
    public int characterReplacement(String s, int k) {
        int n = s.length();
        int[] count = new int[26];
        int maxCount = 0;
        int maxLen = 0;
        int start = 0;

        for (int end = 0; end < n; end++) {
            maxCount = Math.max(maxCount, ++count[s.charAt(end) - 'A']);
            if (end - start + 1 - maxCount > k) {
                count[s.charAt(start) - 'A']--;
                start++;
            }
            maxLen = Math.max(maxLen, end - start + 1);
        }

        return maxLen;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 424 (Longest Repeating Character Replacement)?

This page provides optimized solutions for LeetCode problem 424 (Longest Repeating Character Replacement) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 424 (Longest Repeating Character Replacement)?

The time complexity for LeetCode 424 (Longest Repeating Character Replacement) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 424 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 424 in Java, C++, or Python.

Back to LeetCode Solutions