Longest Single-Letter Substring After at Most k Letter Replacements

You are given a string s made of uppercase English letters and an integer k. You may perform at most k operations. In each operation you pick one position of s and change the letter there to any other uppercase English letter.

Return the length of the longest contiguous substring that can be made to consist of a single repeated letter using at most k operations in total.

Function Signature

def longest_uniform_after_replacements(s: str, k: int) -> int:

Rules

• Only the chosen substring has to end up uniform; letters outside it do not matter, and no operation needs to be spent on them.
• Using fewer than k operations is allowed. With k = 0, the answer is the length of the longest run of one letter already present in s.
• Only the length is returned, not the substring or the letter.

Constraints

• 1 <= len(s) <= 100000
• s contains only the letters 'A' to 'Z'.
• 0 <= k <= len(s)
• The result is an integer from 1 to len(s) inclusive, and it is uniquely determined by the input.

Examples

Example 1

• Input: s = "ABBCB", k = 1
• Output: 4
• Explanation: Changing the C at index 3 to B turns the substring s[1..4] into "BBBB". Making all five letters equal would need at least two changes.

Example 2

• Input: s = "AAAB", k = 0
• Output: 3
• Explanation: No changes are allowed, so the longest existing run, "AAA", is the answer.

Example 3

• Input: s = "XYZXYX", k = 2
• Output: 4
• Explanation: Changing the Y and the Z in s[0..3] = "XYZX" gives "XXXX". Every substring of length 5 or 6 would need at least three changes.

Longest Single-Letter Stretch with Limited Rewrites

You are given a string s of uppercase English letters and an integer k. One operation picks a single position of s and rewrites the letter there as any other uppercase English letter. You may perform at most k operations in total.

Implement longest_uniform_after_replacements(s, k) and return the length of the longest contiguous substring of s that can be turned into one letter repeated throughout, using at most k operations.

Function Signature

def longest_uniform_after_replacements(s: str, k: int) -> int:

Rules

• Only the chosen substring must end up uniform. Letters outside it are irrelevant, and no operation has to be spent on them.
• You may use fewer than k operations. With k = 0, the answer is the length of the longest run of a single letter already in s.
• Return only the length (an integer), not the substring or the letter it becomes.

Output

A single integer from 1 to len(s) inclusive. The answer is uniquely determined by s and k.

Constraints

• 1 <= len(s) <= 100000
• s contains only the letters 'A' to 'Z'.
• 0 <= k <= len(s)
• The result is an integer from 1 to len(s) inclusive.
• Every value involved (lengths, counts, k, the result) is at most 100000, so a 32-bit signed integer is sufficient in every language.

Examples

Example 1

• Input: s = "ABBCB", k = 1
• Output: 4
• Explanation: Rewriting the C at index 3 as B turns s[1..4] into "BBBB". Making all five letters equal would take at least two operations.

Example 2

• Input: s = "AAAB", k = 0
• Output: 3
• Explanation: No operations are allowed, so the longest existing run, "AAA", is the answer.

Example 3

• Input: s = "XYZXYX", k = 2
• Output: 4
• Explanation: Rewriting the Y and the Z in s[0..3] = "XYZX" gives "XXXX". Every substring of length 5 or 6 needs at least three operations.

Hints

1. For one fixed substring, the fewest operations needed equals its length minus the count of its most frequent letter.
2. If a substring can be made uniform within k operations, so can every substring inside it. Think about a window that grows from the right and only moves its left edge when it becomes infeasible.
3. The alphabet has only 26 letters, so per-letter counts for the current window are cheap to maintain.

Approach

A substring can be made uniform with (length - highest letter count) operations, since it is cheapest to keep its most frequent letter and rewrite the rest. The reference keeps a window [left, right] with 26 letter counters and a running max_count, the largest count any letter has reached in any window so far. Each step adds s[right]. If length - max_count exceeds k, the window slides one position (left advances once) instead of shrinking, so its length never drops below the best feasible length found so far. A stale max_count never causes a wrong answer: the window only gets longer when the letter just added reaches a new, larger count, and at that moment the window really is feasible. So the largest window length ever reached is exactly the longest substring that can be made uniform, and the function returns it.

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