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.