Sliding Window - Longest Repeating Character Replacement

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.

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

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.
There may exists other ways to achieve this answer too.

Constraints:

0 <= s.length <= 10⁵
s consists of only uppercase English letters.
0 <= k <= s.length

Solution 1 - Using sliding window technique, and HashMap to store number of times a character appeared

In this approach, we are going to apply sliding window technique, using two pointers left and right, and using a HashMap to store number of times a character appeared in the current window, this tells us the character that appeared more number of times, then check how many other characters are there within that window and see if this count is less than or equal to k.

Implementation steps:

First, we will create five variables left, right that we will use to adjust the window, longestCount to hold the count, that a character appeared maximum number of times in current window, result to hold the final result, and a HashMap count to track each character and number of times that the character appeared.
Next, run a while loop until right pointer reaches end of array, and do the following:
- Check if the current character exists in the count map, if it exists increment its count by 1, otherwise add it to the count map with value as 1.
- After the current character count is added to count map, check if the current character is the one that appeared more number of times, then update longestCount value.
- Next, check if the current window size has at most k replacements, i.e. after subtracting longestCount from current window size (right - left +1) - longestCount > k, this tells us that, how many other characters are there in that window that can be replaced with the character that appeared more number of times.
  For example if the string is AAABBCD and k =3, when we are at character 'D', the character that appeared more number of times is 'A' = 3 and the left pointer will be at 0 and right pointer will be at 6, so within this window 6 -0 +1 (+1 is because the array is 0-indexed) which is 7, and if we subtract A's count then the result will be 7 - 3 = 4, now we know that there are more than k elements that need to be replaced, we can now reduce the count of left most indexed character, and also reduce the left counter.
- Now, the window size has at most k character replacements, so update the result by taking the maximum from result (current result) and the current window right -left +1, and then increment the right pointer to go to the next character.
Finally, return the result.

import java.util.HashMap; public class LongestRepeatingCharacterReplacement { static int characterReplacement(String s, int k) { HashMap<Character, Integer> count = new HashMap<>(); int left = 0; int right = 0; int longestCount= 0; int result = 0; while(right < s.length()) { char current = s.charAt(right); int newCount = count.merge(current, 1, Integer::sum); // add count as 1 if not exists, // otherwise sum it up to existing count. longestCount = Math.max(longestCount, newCount); /* Key logic is here, Since we can perform K number of replacements, our window size is right-left, check if there are 'K' other elements other than the character which appeared the highest number of times. For example, ABBBBBBCDEF, K=2, when we are at C, our window size is 8, and the character that appeared higher number of times is 'B', within this window, we have two other characters A and C. so the longest substring with K replacements at this window will be BBBBBBBBDEF. */ if((right - left +1) - longestCount > k) { count.merge(current, -1, Integer::sum); left++; } result = Math.max(result, (right - left +1)); right++; } return result; } public static void main(String[] args) { System.out.println(characterReplacement("ABAB", 2)); System.out.println(characterReplacement("AABABBA", 1)); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of input string s.
Space complexity: O(1), since the input can contain only uppercase English letters, so the HashMap is going to contain at most 26 entries. ()

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: