Longest Substring with At Most K Character Changes
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.
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.
s: A string consisting only of uppercase English letters.k: An integer representing the maximum number of character changes allowed.k characters to a single, repeating character.s will only contain uppercase English letters ('A' through 'Z').k can be 0, meaning no changes are allowed.s is empty, the result should be 0 (though constraints specify s.length >= 1).Examples
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.
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.
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
1 <= s.length <= 10^50 <= k <= s.lengths consists of only uppercase English letters.k=0 and scenarios where k is very large.Loading editor...