Back to Sliding Window
Medium
Longest Repeating Character Replacement
You are given a string `s` and an integer `k`. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most `k` times. Return the length of the longest substring containing the same letter you can get after performing the above operations.
Examples
Input:s = "ABAB", k = 2
Output:4
Replace the two 'A's with two 'B's or vice versa.
Input:s = "AABABBA", k = 1
Output:4
Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4. There may exists other ways to achieve this answer too.
Constraints
1 <= s.length <= 10^5s consists of only uppercase English letters.0 <= k <= s.length
Approach
Check every possible substring. For each substring, count the frequency of each character. The minimum number of replacements needed to make all characters in the substring identical is `length_of_substring - max_frequency`. If this value is less than or equal to `k`, the substring is valid. Update the maximum length found so far.
Complexity Analysis
Time Complexity
O(n^2)
Space Complexity
O(1)
This approach is slow and leads to Time Limit Exceeded (TLE) on large inputs.
Solution.java
class Solution { public int characterReplacement(String s, int k) { int maxLength = 0; for (int i = 0; i < s.length(); i++) { int[] counts = new int[26]; int maxFreq = 0; for (int j = i; j < s.length(); j++) { counts[s.charAt(j) - 'A']++; maxFreq = Math.max(maxFreq, counts[s.charAt(j) - 'A']); int len = j - i + 1; if (len - maxFreq <= k) { maxLength = Math.max(maxLength, len); } } } return maxLength; }}