Frontend School

Longest Substring After K Replacements

DSA
medium

Longest Substring After K Replacements

Medium
String
Two Pointers
Sliding Window
Hash Map

Overview

In various LinkedIn applications, such as content moderation, search indexing, or profile parsing, efficiently processing and transforming text sequences is crucial. This problem focuses on identifying patterns within strings that can be normalized or optimized with a limited number of changes. Your task is to find the longest possible contiguous sequence of characters that can be made uniform (all same character) by changing at most k characters within that sequence. This challenges your ability to apply efficient string manipulation techniques.

What you need to do / Task

Implement a function characterReplacement that takes a string s and an integer k. The function should return the length of the longest substring of s where, by changing at most k characters within that substring, all characters in it become identical.

Input & output

  • s: A string consisting of uppercase English letters.
  • k: An integer representing the maximum number of character replacements allowed.

Returns: An integer, the length of the longest substring satisfying the condition.

Clarifications

  • An empty string s or k=0 should be handled correctly.
  • k can be large enough to change an entire string.
  • The characters in s are always uppercase English letters ('A' through 'Z').

Examples

1

Example 1

Input:

s = "ABAB", k = 2

Output:

4

Note:

Replace the two 'A's with 'B's or two 'B's with 'A's to get 'BBBB' or 'AAAA'. The longest substring is of length 4.

2

Example 2

Input:

s = "AABBC", k = 1

Output:

4

Note:

Consider the substring 'AABB'. With k=1, we can change one 'B' to 'A' (or one 'A' to 'B') to get 'AAAB' or 'BBBA'. The length is 4. Another example: 'BBCA', change 'A' to 'B' -> 'BBBB', length 4.

3

Example 3

Input:

s = "ABCDE", k = 0

Output:

1

Note:

No replacements allowed. The longest repeating character substring is any single character, length 1.

Constraints

Constraints & assumptions

  • 1 <= s.length <= 10^5
  • s consists of only uppercase English letters.
  • 0 <= k <= s.length

Out of scope

  • Case sensitivity (assume uppercase only).
  • Non-alphabetic characters.
  • Optimizing for memory beyond standard O(1) or O(alphabet_size) for frequency maps.

What interviewers evaluate

  • Ability to identify and apply the Two Pointers (Sliding Window) pattern.
  • Correctness in handling window expansion and contraction logic.
  • Efficiency of the solution, aiming for O(N) time complexity.
  • Clarity and readability of the code, including proper variable naming.

Loading editor...