3. Longest Repeating Character Replacement

Description

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

Constraints:

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

Approach

• In any window we try to maintain the most frequent element that way if we subtract max element frequency from window size then we know the remaining ones need to be replaced in order to have String with only one character.
• Now we check if that difference is greater than what is allowed if yes then we just move left pointer and update frequency accordingly and then we have a valid window and check max
• For our if condition we maintain max frequency we only need to update for max but not when frequency decreases because we only care about max because of the condition
• Time:O(n) Space:O(26)

class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int longest = 0;
        int left = 0;
        int max = 0;
 
        for (int right = 0; right < s.length(); right++) {
            count[s.charAt(right) - 'A']++;
            max = Math.max(max,count[s.charAt(right) - 'A']);
            if (right - left + 1 - max > k) {
                count[s.charAt(left) - 'A']--;
                left++;
            }
            longest = Math.max(longest, right - left + 1);
        }
 
        return longest;
    }
}