PIXELBANKv8.2.1
Menu
Sign In

Longest Repeating Character Replacement

MediumSliding Window

Given a string s and an integer k, you can choose any character and change it to any other uppercase English letter at most k times.

Return the length of the longest substring containing the same letter after performing at most k replacements.

Example:

Input:
AABABBA
1
Output:
4
Reasoning:
  • We start with the input string AABABBA and the replacement limit k = 1.
  • We try to find the longest substring with the same letter after at most k replacements. The substring AABBB can be formed by replacing one A with a B, resulting in a substring of length 44 with the same letter B if we consider AABBB as BBBB after replacement, but since we are considering AABABBA we look at AABB and BBBA and see AABB can become AAAA or BBBB with one replacement.
  • Considering all possible substrings, we find that the longest one with the same letter after at most 1$ replacement is of length $4$, which can be achieved by replacing one character in AABBto getAAAAor inBBBAto getBBBB`.
  • The final output is 44.

Constraints:

  • 1 <= len(s) <= 10^5
  • s consists of uppercase English letters
  • 0 <= k <= len(s)
Editor

Test Results

0/0
Run code to see test results.