Pinduoduo: Longest Single-Letter Substring After at Most k Character Changes

Quick Overview

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.

Longest Single-Letter Substring After at Most k Character Changes

Company: Pinduoduo

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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 ```python 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** ```text 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** ```text 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** ```text Input: s = "BAAAB", k = 0 Output: 3 ``` With no changes allowed, the longest run is the existing `"AAA"`.

Overview: 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. Implement `longest_uniform_after_changes(s, k)`, which returns this length as an integer. ### 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. The answer is always between `1` and `len(s)`, so it never exceeds `10^5` and fits in a 32-bit signed integer in every language. ### Constraints - `1 <= len(s) <= 10^5` - `s` consists only of the uppercase letters `'A'` to `'Z'`. - `0 <= k <= len(s)` ### Examples **Example 1** ```text 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** ```text 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.

Constraints

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

Examples

Input: ('ABAB', 2)

Expected Output: 4

Explanation: Source example 1: change both B's (or both A's) so the whole string of length 4 is one letter.

Input: ('AABABBA', 1)

Expected Output: 4

Explanation: Source example 2: changing index 3 to B gives BBBB; every length-5 window needs 2 changes, so the window must shrink.

Hints

Fix one substring. How many changes does it take to turn it into a single repeated letter, and which letter should you keep?
A substring of length L can be made uniform exactly when L minus the count of its most common letter is at most k.
Changing characters outside the substring you keep never helps, so you only need to reason about one contiguous range at a time.

Approach

Key fact: for a fixed substring, the cheapest way to make it one repeated letter is to keep its most frequent letter and change every other character, and changes outside the substring never help. So a substring of length L is achievable exactly when L minus the count of its most frequent letter is at most k.

Algorithm: slide a window [left, right] over s with 26 letter counters. For each right, add s[right] and update top, the largest single-letter count ever seen in the window. While (window length - top) > k, drop s[left] and advance left. Then record the window length as a candidate answer.

No overshoot: top only grows, so the shrink test can be looser than the true test. But top was set when a window containing top copies of one letter c had length at most top + k. That window was valid at that moment. Extending it to length min(len(s), top + k) adds at most k minus its current non-c count in new characters, so a valid substring at least as long as any recorded length exists.

No undershoot: let [a, b] be an optimal substring. While right <= b, left can never move past a. Moving past a would need (r - a + 1) - top > k, but [a, r] lies inside a valid substring and top is at least its true maximum count. So when right reaches b, the window has length at least b - a + 1.

Each index enters and leaves the window at most once.

Edge cases: k = 0 gives the longest existing run, k = len(s) gives len(s), and a singleton gives 1. The answer always lies in [1, len(s)].

Time complexity:

O(n)

Space complexity:

O(1)