Practice/Meta/Leetcode 424. Longest Repeating Character Replacement

Leetcode 424. Longest Repeating Character Replacement

CodingMust

Problem

You are given a string s consisting of uppercase English letters and a non-negative integer k. You can choose any character in the string and change it to any other uppercase English letter. This operation can be performed at most k times.

Your task is to find the length of the longest substring that contains only one distinct character after performing at most k character changes.

Requirements

1. Find the maximum length substring where all characters can be made identical
2. You may perform at most k character replacements
3. Return the length of the longest such substring
4. The string contains only uppercase English letters (A-Z)

Constraints

• 1 ≤ length of s ≤ 10^5
• 0 ≤ k ≤ length of s
• s contains only uppercase English letters
• Time complexity: O(n) where n is the length of the string
• Space complexity: O(1) or O(26) for character frequency tracking

Examples

Example 1:

Input: s = "AABABBA", k = 1 Output: 4 Explanation: Replace the 'B' at index 2 with 'A', resulting in "AAAAABBA". The substring "AAAA" has length 4.

Example 2:

Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'B's with 'A's to get "AAAA", or replace the two 'A's with 'B's to get "BBBB". Either way, the entire string becomes uniform with length 4.

Example 3:

Input: s = "AABCCBB", k = 2 Output: 5 Explanation: Consider the substring "CCBB" and replace both 'C's with 'B's to get "BBBB", or take "AABCC" and replace both 'C's with 'A's or 'B's. The maximum length achievable is 5.