Longest Repeating Character Replacement

Mediumsliding windowGoogleAmazonMicrosoft

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.

Examples

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 one 'A' in 'AABA' → 'AAAA' or replace one 'B' in 'ABBB' → 'BBBB'.

Constraints

1 <= s.length <= 10^5
s consists of only uppercase English letters
0 <= k <= s.length

💡 Hints

Hint 1

Use a sliding window and track the frequency of each character inside the window.

Hint 2

The key insight: windowSize - maxFreqInWindow <= k means the window is valid.

Hint 3

If invalid, shrink from the left.

Algorithm Complexity

Official asymptotic Big-O runtime and auxiliary memory analysis

Linear

Algorithmic Approach

Sliding window tracking character frequencies. Window is valid if (windowSize - maxFreq) <= k. If invalid, shrink left. Track maximum valid window size.

Time ComplexityO(n)

Why:

The right window boundary advances across string of length n while the left boundary only slides forward, visiting each char at most twice.

Space ComplexityO(1)

Why:

A frequency count map/array stores at most 26 uppercase English letters, consuming O(1) fixed space.

Big-O Growth CurveLinear (O(N))

Execution time scales directly in proportion to the input size.

🌍 Real-World Use Cases

BioinformaticsDNA sequence matching

Finding the longest segment of a DNA strand that can be made uniform with at most k mutations — directly maps to this problem.

🔍 Dry Run

Solution⏱ O(n) | 💾 O(1)

Line2

count={}object

left=0number

maxFreq=0number

maxLen=0number

Initialize. Input: 'AABABBA', k=1.