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.

給一個字串 s 可以隨意變換 s 中的字元 k 次，找到相同字源的最長長度。

Example

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

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.

Coding

var characterReplacement = function(s, k) {
  let l = 0, max = 0, mostCounts = 0, map = {};
  for (let r = 0; r < s.length; r++) {
    if (!map[s[r]]) map[s[r]] = 1;
    else map[s[r]]++;

    mostCounts = Math.max(mostCounts, map[s[r]]);

    if ((r - l + 1) - mostCounts > k) {
      map[s[l]]--;
      l++;
    }
    max = Math.max(max, r - l + 1);
  }
  return max;
};

1. R = 0, L = 0

• map = { 'A': 1 },
• mostCounts = 1
• sub-string = 'A'
• sub-string length = 1
• (sub-string length) - 1 < 1

2. R = 1, L = 0

• map = { 'A': 2 },
• mostCounts = 2
• sub-string = 'AA'
• sub-string length = 2
• (sub-string length) - 2 < 1

3. R = 2, L = 0

• map = { 'A': 2, 'B': 1 },
• mostCounts = 2
• sub-string = 'AAB'
• sub-string length = 3
• (sub-string length) - 2 = 1

4. R = 3, L = 0

• map = { 'A': 3, 'B': 1 },
• mostCounts = 3
• sub-string = 'AABA'
• sub-string length = 4
• (sub-string length) - 3 = 1

5. R = 4, L = 0

• map = { 'A': 3, 'B': 2 },
• mostCounts = 3
• sub-string = 'AABAB'
• sub-string length = 5
• (sub-string length) - 3 > 1 (X) 移除 sub-string 的第一個字元, L 往右移動一格

6. R = 5, L = 1

• map = { 'A': 2, 'B': 3 },
• mostCounts = 3
• sub-string = 'ABABB'
• sub-string length = 5
• (sub-string length) - 3 > 1 (X) 移除 sub-string 的第一個字元, L 往右移動一格

7. R = 6, L = 2

• map = { 'A': 2, 'B': 3 },
• mostCounts = 3
• sub-string = 'BABBA'
• sub-string length = 5
• (sub-string length) - 3 > 1 (X) 移除 sub-string 的第一個字元, L 往右移動一格

Time complexity: O(n)