‹ DS&A interview · Socratic
DSA · Sliding Window · #104

Longest Repeating Character Replacement

Module 71 · difficulty 3/5·⏱ 30:00starts on first keystroke

You are given a string `s` consisting of uppercase English letters and an integer `k`. You may choose any character of the string and change it to any other uppercase English letter. You can perform this operation at most `k` times. Implement `characterReplacement(s, k)` that returns the length of the longest substring containing the **same letter** you can obtain after performing the above operations.

Examples
  • s = "ABAB", k = 2 → 4 — Replace the two 'A's with 'B's, or vice versa, to get "BBBB" (or "AAAA").
  • s = "AABABBA", k = 1 → 4 — Replace the one 'A' in the middle with 'B' to form "AABBBBA". The substring "BBBB" has length 4.
  • s = "AAAA", k = 0 → 4 — No replacements needed; the whole string is already uniform.
Constraints
  • · 1 <= s.length <= 10^5
  • · s consists of only uppercase English letters.
  • · 0 <= k <= s.length
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.