Longest Repeating Character Replacement

Leet code Link - https://leetcode.com/problems/longest-repeating-character-replacement/description/

Complexity - Medium

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 <= 105
s consists of only uppercase English letters.
0 <= k <= s.length

Solution

We know that the solution is valid if the length of the window minus most frequent element gives the less frequent element that should be replaced with k times. so if it is greater than k then the window is invalid.

As you can see we have to track the count of elements so we use hashmap.

We can use sliding window where we increment left pointer when the window is invalid and decrement the map value as we remove the left element.

class Solution {
    public int characterReplacement(String s, int k) {
        HashMap<Character,Integer> map = new HashMap<>();
        int l=0;int maxf = 0;int res = 0;
        for(int r=0;r<s.length();r++){
            map.put(s.charAt(r),map.getOrDefault(s.charAt(r),0)+1);
            maxf = Math.max(maxf,map.get(s.charAt(r)));

            while((r-l+1)-maxf>k){
                map.put(s.charAt(l),map.get(s.charAt(l))-1);
                l++;
            }
            res = Math.max(res, r-l+1);
        }
        return res;
    }
}

Complexity

time Complexity - O(N)

Space complexity - O(m) - m is unique characters