PPractick

The problem

A DNA-editing tool can change up to k letters in a sequence, and researchers want the longest stretch that can be made all the same letter. A window can be made uniform when window length − (count of its most frequent letter) ≤ k, since exactly the non-majority letters need replacing. A sliding window grows to the right and shrinks from the left whenever it needs more than k replacements, tracking letter counts to find the most frequent letter.

Example: s = "AABABBA", k = 1 → 4 ("AABA" → "AAAA").

Function signature

int characterReplacement(const string& s, int k);  // uppercase letters A-Z

Test cases

Input (s, k)	Output	Explanation
("ABAB", 2)	4	Replace both As (or both Bs)
("AABABBA", 1)	4	"AABA" becomes "AAAA"
("AAAA", 0)	4
("ABCDE", 1)	2
("ABBB", 0)	3
("A", 0)	1

(Confirm: replacements can turn a letter into any other letter; at most k replacements; the substring must be contiguous.)

How interviewers phrase it

• "You can replace at most k characters of s with any uppercase letter. Return the length of the longest substring containing the same letter" (LeetCode 424).

Clarifying questions to ask

1. What alphabet? (Uppercase A–Z, so 26 counters.)
2. At most k replacements, not exactly k?
3. Contiguous substring? (Yes.)

Follow-ups to expect

1. "When is a window fixable?"
2. "Why is shrinking from the left safe?"
3. "Can you avoid recomputing the max over 26 letters?"
4. "What if the alphabet were large?"
5. "Complexity?"

Related questions

• Longest Substring With At Most K Distinct Characters Hard
• Minimum Window Substring Hard
• Number of Substrings Containing All Three Characters Hard
• Minimum Window Subsequence Hard
• Isomorphic String Easy
• Check if two strings are anagram of each other Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in