Microsoft: Longest Single-Letter Substring After at Most k Letter Replacements

Quick Overview

A string problem: given uppercase letters and a budget of k single-letter changes, find the longest contiguous substring that can be turned into one repeated letter. It tests efficient substring scanning with letter counts and careful reasoning about when a candidate substring stays valid.

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 Substring After at Most k Letter Replacements