Developers

Longest Repeating Character Replacement

MediumSliding windowAlso known as LeetCode 424

You are given a string s of uppercase English letters and an integer k. You may choose any letter of s and change it to any other uppercase letter, at most k times in total.

Return the length of the longest substring that contains only one distinct letter after performing these changes.

Examples

Input s = "ABAB", k = 2
Output 4
Change both As to B, or both Bs to A.
Input s = "AABABBA", k = 1
Output 4
Change the B in AABA to A to get AAAA, or the A in BABB to B to get BBBB.
Input s = "AAAA", k = 0
Output 4

Constraints

  • 1 <= s.length <= 100,000
  • s consists only of uppercase English letters
  • 0 <= k <= s.length

Stuck? Take one hint at a time

Common mistakes
  • Computing the cost as the number of letters that are not the first letter of the window, instead of the most common letter.
  • Scanning all 26 counts for the most common letter at every step. It is correct and still linear, but about 26 times slower than keeping one number.
  • Forgetting to remove the letter at the left end from the counts when the window shrinks, so the counts describe a window that no longer exists.
  • Recomputing the true most common count after every removal. It is correct, but it costs 26 steps each time, and the stale maximum makes it unnecessary.
  • Counting the window length as right - left instead of right - left + 1.
Questions an interviewer may ask next
  • The alphabet is large (any Unicode letter). Which approach still works well, and what changes? (The first, with a map of counts in place of the 26 slots. The stale maximum idea needs no change.)
  • Return the window itself (start and length) as well as its length.
  • You may only change letters to a letter that is already in the substring. Does the answer change?
  • Why is it safe not to lower maxCount when the window shrinks? Give the argument.