Find longest uniform substring after k replacements

Q: Find longest uniform substring after k replacements

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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).

Find longest uniform substring after k replacements

Overview

Comments (0)