How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Apple.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Apple during technical interviews.

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.

Input: ("abcd", 1)

Expected Output: 2

Explanation: All distinct, so any length-2 window needs exactly 1 replacement; length 3 would need 2 > k.

Input: ("", 0)

Expected Output: 0

Explanation: Empty string has no substring; answer is 0.

Input: ("AAAA", 0)

Expected Output: 4

Explanation: Already uniform; no replacements needed, whole string qualifies.

Input: ("ABAB", 2)

Expected Output: 4

Explanation: Replace the two 'B's (or two 'A's) using k=2 to make the whole string uniform.

Input: ("A", 0)

Expected Output: 1

Explanation: Single character is trivially uniform.

Input: ("ABCDE", 0)

Expected Output: 1

Explanation: All distinct with no replacements allowed; only single characters are uniform.

Input: ("AABABBA", 0)

Expected Output: 2

Explanation: With k=0, the longest existing run of one character is the 'BB' (or 'AA'), length 2.

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.

Quick Overview

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.