Frontend School

Longest Substring with At Most K Character Changes

DSA
medium

Longest Substring with At Most K Character Changes

Medium
Sliding Window
String
Hash Map

Overview

In a hypothetical ServiceNow analytics engine, we often process large strings representing log data or user input sequences. To optimize storage and improve search performance, we sometimes need to identify the longest continuous segments within these strings that could be made uniform with a minimal number of modifications. This problem challenges you to find the longest possible substring that can be made into a single repeating character, given a budget k for character changes.

What you need to do / Task

Implement the function findLongestSubstring that takes a string s and an integer k. Your task is to return the length of the longest substring you can obtain where all characters in that substring are the same, by changing at most k characters within that substring.

Input & output

  • Input:
    • s: A string consisting only of uppercase English letters.
    • k: An integer representing the maximum number of character changes allowed.
  • Output: An integer, representing the length of the longest substring that can be formed by changing at most k characters to a single, repeating character.

Clarifications

  • The input string s will only contain uppercase English letters ('A' through 'Z').
  • k can be 0, meaning no changes are allowed.
  • If s is empty, the result should be 0 (though constraints specify s.length >= 1).
  • You can change any uppercase English character to any other uppercase English character.

Examples

1

Example 1

Input:

s = "AABABBA", k = 1

Output:

4

Note:

If we change the 'B' at index 2 to 'A', the string becomes "AAAABBA". The longest substring of 'A's is "AAAA", with length 4. Similarly, we could change the 'B' at index 4 to 'A' to get "AABAA BA", or change 'A' at index 0 to 'B' to get "BABABBA". The maximum length achievable is 4.

2

Example 2

Input:

s = "ABABA", k = 2

Output:

5

Note:

We can change the two 'B's to 'A's to get "AAAAA", or change the three 'A's to 'B's to get "BBBBB". In both cases, the longest substring has length 5.

3

Example 3

Input:

s = "AAAB", k = 0

Output:

3

Note:

No changes are allowed. The longest substring with repeating characters is "AAA", which has a length of 3.

Constraints

Constraints & assumptions

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

Out of scope

  • Handling non-uppercase English characters or non-string inputs.
  • Considering case sensitivity (all inputs are uppercase).

What interviewers evaluate

  • Correctness of the sliding window algorithm and its application.
  • Efficient use of data structures for character frequency tracking.
  • Effective handling of edge cases, including k=0 and scenarios where k is very large.
  • Optimization for time and space complexity.

Loading editor...