Skip to content

424. Longest Repeating Character Replacement

Source: https://leetcode.com/problems/longest-repeating-character-replacement/description/

Intuition

Approach

For this question, we use two pointer approach. By move the lower pointer and higher pointer,

Complexity

  • Time complexity: \(O(n)\)
  • Space complexity:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int characterReplacement(String s, int k) {
    int max = 0;
    int res = 0;
    int i = 0;
    int j = 0;
    int[] arr = new int[26];
    while (i < s.length()) {
        arr[s.charAt(i) - 'A']++;
        // record the max repeat number in the substring
        // we only need to replace the rest letters in this 
        // substring
        max = Math.max(max, arr[s.charAt(i) - 'A']);
        // Number of replacement need
        if (i - j + 1 - max > k) {
            // if the need > restrict,
            // move the lower pointer right
            arr[s.charAt(j) - 'A']--;
            j++;
        }
        // update the length of substring in the interating
        // process
        res = Math.max(i - j + 1, res);
        i++;
    }
    return res;
}