Longest Repeating Character Replacement

MediumSliding Windowlongest-repeating-character

You are given a string s consisting only of uppercase English letters, and an integer k. You can choose up to k characters of the string and replace them with any other uppercase English letters.

After performing at most k replacements, return the length of the longest substring containing only one distinct character.

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the 2 'B's with 'A's to get the string "AAAA".

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the 1 'B' with 'A' to get the substring "AAAA".
Recommended time and space complexity

You should aim for a solution with O(n) time complexity and O(1) space complexity, where n is the length of the input string.

Hint 1

Try using the sliding window technique. Maintain a window where after k replacements, all characters are the same.

Hint 2

In each window, it's important to know how many times the most frequent character appears. The difference between the window size and the frequency of the most frequent character is the minimum number of replacements needed to get a string of identical characters.

Hint 3

Use a hash table to count character frequencies in the current window. When (window_size - max_frequency) > k, you need to shift the left boundary of the window.

This problem tests skills in working with strings and optimization using the sliding window technique. It helps develop understanding of algorithmic complexity and working with substrings. The solution requires an efficient approach to counting character frequency and managing window size.
solution.js · saved

Input

"ABAB", 2

Expected Output

4