Longest Repeating Character Replacement

Medium

Sliding Window

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1

Input: s = "ABAB", k = 2

Output: 4

Explanation: Replace the two "A"s with two "B"s or vice versa.

Example 2

Input: s = "AABABBA", k = 1

Output: 4

Explanation: Replace the one "A" in the middle with "B" and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4.

Constraints

•1 <= s.length <= 10^5
•s consists of only uppercase English letters.
•0 <= k <= s.length

Show Hints (3)

Hint 1: Use a sliding window and track the frequency of each character.

Hint 2: The window is valid if: windowSize - maxFrequency <= k

Hint 3: If the window becomes invalid, shrink it from the left.

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?