Find longest uniform substring after k replacements
Company: Apple
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a string s (ASCII, length up to 2e5) and integer k (0 ≤ k ≤ |s|), return the length of the longest substring that can be turned into all the same character by replacing at most k characters.
Constraints and requirements:
- Time O(n), space O(1) amortized (treat alphabet size as constant).
- Explain why a sliding window with a running max‑frequency works and why shrinking the window preserves correctness even as the max frequency may lag.
- Provide examples: s="AABABBA", k=1 ⇒ 4; s="aaabbc", k=2 ⇒ 5; s="abcd", k=1 ⇒ 2.
- Implement in your preferred language and discuss edge cases (k=0, all identical chars, very large n).
Quick Answer: This question evaluates skills in string processing, frequency analysis, and algorithmic optimization within the Coding & Algorithms domain, focusing on practical application of linear-time, constant-space techniques.
Given a string `s` (ASCII, length up to 2e5) and an integer `k` (0 <= k <= |s|), return the length of the longest substring that can be turned into all the same character by replacing at most `k` characters.
Use a sliding window with a running max-frequency: expand the right edge, track the count of each character in the window and the highest single-character frequency seen so far (`maxFreq`). The number of characters that must be replaced to make the window uniform is `windowLength - maxFreq`. While that exceeds `k`, shrink the window from the left. The answer is the largest valid window length.
The window length never decreases because once we find a window of a given size, we only slide it (advancing left in lockstep with right) — so even though `maxFreq` may lag (we never decrease it when shrinking), the recorded best is preserved. A stale `maxFreq` can only make the validity check stricter, never looser, so it cannot inflate the answer.
Examples:
- s = "AABABBA", k = 1 => 4
- s = "aaabbc", k = 2 => 5
- s = "abcd", k = 1 => 2
Edge cases to consider: k = 0 (no replacements, longest run of one char), all identical characters (whole string), and very large n (must be O(n)).
Constraints
- 1 <= |s| <= 2 * 10^5 (s may also be empty)
- s consists of ASCII characters
- 0 <= k <= |s|
- Required time complexity: O(n)
- Required space complexity: O(1) amortized (alphabet size treated as constant)
Examples
Input: ("AABABBA", 1)
Expected Output: 4
Explanation: Replace one character to get a run of 4 identical chars (e.g. AABABBA -> AAAA-window over 'AABA' or 'ABBA' yields length 4).
Input: ("aaabbc", 2)
Expected Output: 5
Explanation: Window 'aaabb' (length 5): replace the two 'b's with 'a' using k=2 replacements.
Hints
- Slide a window over s and keep a count of each character inside it.
- Track the highest single-character frequency in the window (maxFreq). The cost to make the window uniform is windowLength - maxFreq; the window is valid when that cost is <= k.
- When the window becomes invalid, advance the left pointer. You never need to decrease maxFreq when shrinking — a stale maxFreq only makes the validity test stricter, never looser, so it cannot overcount.