Katkat
Back

Longest Single-Letter Substring After at Most k Character Changes

PinduoduoSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Given a string of uppercase letters and a budget of at most k single-character changes, find the longest run of one repeated letter that can be produced. Tests reasoning about which substrings can be made uniform, efficient counting, and a near-linear solution for strings of up to 100,000 characters.

You are given a string s of uppercase English letters and an integer k. You may perform at most k operations; each operation changes one character of s into any other uppercase English letter. Return the length of the longest substring, made of one letter repeated, that you can obtain.

The report says only that "some" characters may be changed. This version makes the budget an explicit parameter k, since with an unlimited budget the whole string would always qualify, and it assumes an uppercase English alphabet.

Function Signature

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

Rules

  • A substring is a contiguous, non-empty part of s.
  • Changes are made in place, so the length of s never changes.
  • You may use fewer than k operations, including none.
  • Return the largest length achievable over every way of using at most k operations.

Constraints

  • 1 <= len(s) <= 10^5
  • s consists only of the uppercase letters 'A' to 'Z'.
  • 0 <= k <= len(s)

Examples

Example 1

Input: s = "ABAB", k = 2
Output: 4

Changing both 'B' characters to 'A' (or both 'A' characters to 'B') makes the whole string one letter.

Example 2

Input: s = "AABABBA", k = 1
Output: 4

Changing the 'A' at index 3 to 'B' gives "AABBBBA", which contains "BBBB". No single change produces a longer run.

Example 3

Input: s = "BAAAB", k = 0
Output: 3

With no changes allowed, the longest run is the existing "AAA".