noodleProblems/
Longest Repeating Character Replacement
#113

Longest Repeating Character Replacement

AlgorithmmediumHash TableStringSliding Window

You are given a string s and an integer k. You may choose any character of s and change it to any other uppercase English letter; you can perform this operation at most k times.

Return the length of the longest substring that, after at most k such replacements, contains only one distinct character.

Example cases

  • replace both ends
    in s = "ABAB", k = 2
    out 4
    Replace the two "A"s with "B"s (or vice versa) to get "BBBB" — length 4.
  • one replacement
    in s = "AABABBA", k = 1
    out 4
    Replace the middle "A" to form "AABBBBA"; the run "BBBB" has length 4.
  • no replacements allowed
    in s = "AAAA", k = 0
    out 4
    Already all the same — the whole string qualifies with zero changes.

Constraints

  • 1 <= s.length <= 10^5
  • `s` consists of uppercase English letters.
  • 0 <= k <= s.length
Saved
s =
"ABAB"
k =
2