LeetCode problem 424 Longest Repeating Character Replacement(Java)

Source Url:https://leetcode.com/problems/longest-repeating-character-replacement/

Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

Note:
Both the string’s length and k will not exceed 104.

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.

This problem is a standard resizable sliding window problem.

Every time when a character moves into the window, we need to count how many characters we can replace. We need to replace the inference character. For example “ABCCD”, if we can replace 3 characters, we must keep “CC” unchanged, replace “ABD” as “CCC”. When replaced characters are more than the value of k, we need to move left to let a character out of the window.

So function characterReplacement is very familiar (see also).

Then is function replaceCount to count we need to replace how many characters to make sure all characters is the same.

Running time is 30ms.

Code download address: https://github.com/tinyfool/leetcode/tree/master/src/p0424

Want to know details of the sliding window algorithm, check my post: The Sliding Window Algorithm for string and array.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.