Longest Repeating Character Replacement — Medium Coding Interview Question

You are given a string s and an integer k. You can choose any character and change it to any other uppercase English character, at most k times. Return the length of the longest substring containing the same letter after performing the above operations.

Example

Input: s = "ABAB", k = 2

Output: 4

Constraints

• 1 ≤ s.length ≤ 10⁵
• s consists of only uppercase English letters
• 0 ≤ k ≤ s.length

Topics & Companies

Topics: strings, sliding-window

Asked by: Amazon, Google, Meta, Microsoft

Optimal Solution Complexity

Time complexity: O(n). Space complexity: O(1).

Practice more

• All DSA Problems
• DSA Patterns