28 Sep 2023, 9:50 PM
28 Sep 2023, 9:50 PM

14. Longest Repeating Character Replacement

#leetcode/424

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:

Input: s = "AABABBA", k = 1
Output: 4

Solution

Solution in C++ using hash map

The idea is to iteratively find the longest substring by maintaining a sliding window approach. We use two pointers (low and high) to represent the boundaries of the current substring we are checking, and a hash map (in our case an array of 26 elements) to count the frequency of each character. As we iterate through the string, we update the pointers and adjust the window when the condition high - low + 1 - maxFreq <= k isn't true. In fact, to obtain the longest substring, we have to rely on the character with the max frequency and if we find another character we can try to substitute it using k. When we can't use k anymore, we have to reduce our sliding window from left, until high - low + 1 - maxFreq <= k is true.

Graphic explanation:

Drawing canvas

Here's the implementation:

int characterReplacement(string s, int k) {
	array<int, 26> charSet = {};
	int n = s.size(), maxFreq = 0, maxLength = 0;
	for(int low = 0, high = 0; high < n; high++) {
		char currChar = s[high];
		charSet[currChar - 'A']++;
		maxFreq = max(maxFreq, charSet[currChar - 'A']);
		while(high - low + 1 - maxFreq > k) {
			charSet[s[low] - 'A']--;
			low++;
		}
		maxLength = max(maxLength, high - low + 1);
	}
	return maxLength;
}