[Leetcode] 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.

Analysis:

The basic idea is to iterate all substring which could satisfy the condition.  That is, the substring would become repeating character string if k characters were replaced. If we have count of all substring characters, we know that the maximum number of characters to be replaced = the total number of characters - the max number of any single letter. It would takes O (n^2 * k) time.

We can improve the performance. Notice that if substring(i, j) is a repeating character string and substring(i, j+1) is not, then all substring(i, j+n) will not be a repeating character as well. So we have to increase the i to have another repeating character substring. It is actual a slide window and takes O(n*k) time. 

    int getCount(Map<Character, Integer> m, int k) {
        
        int maxVal = 0;
        int total = 0;
        
        for(Character c: m.keySet()) {
            total += m.get(c);
            maxVal = Math.max(maxVal, m.get(c));
        }

        if (total - maxVal > k)
            return -1;
        
        return total;
    }

    public int characterReplacement(String s, int k) {
        int ret = 0;
        int i = 0;
        int j = 0;

        Map<Character, Integer> m = new HashMap<>();
        while(j < s.length()) {
            m.put(s.charAt(j), m.getOrDefault(s.charAt(j), 0) + 1);
            int count = getCount(m, k);
            //if not satisfied, shrink the windows by increasing i
            if (count < 0) {
                while(i < j && count < 0) {
                    m.put(s.charAt(i), m.get(s.charAt(i)) - 1);
                    count = getCount(m, k);
                    i++;
                }
            }
            ret = Math.max(ret, count);
            j++;
        }
        
        return ret;
    }