Problem

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

Example 1:

1
2
3

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

1
2
3
4
5

Input: s = "AABABBA", k = 1
Output: 4
Explanation: 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.

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Sliding window

This problem is a variant of the problem Longest Substring Without Repeating Characters. We will use a similar sliding-window technique to solve this problem.

Method 2 - Sliding Window with max frequency calculation

Here is the approach:

  1. Sliding Window Technique:
    • Use two pointers (left and right) to represent a sliding window.
  2. Keep a Frequency Count:
    • Use a frequency map or array to track the count of characters in the current window.
  3. Valid Substring Check:
    • Ensure the number of changes required (length of window - frequency of the most common character in the window) does not exceed k.
  4. Expand and Contract the Window:
    • Expand the window by moving right.
    • If the window becomes invalid, move left to shrink it.
  5. Track the Maximum Length:
    • Continuously update the maximum length of a valid window.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

ous(substring: str, k: int) -> bool:
freq = [0] * 26
for char in substring:
    freq[ord(char) - ord('A')] += 1
max_freq = max(freq)
return len(substring) - max_freq <= k

def characterReplacement(s: str, k: int) -> int:
	max_length = 0
	for i in range(len(s)):
	    for j in range(i, len(s)):
	        if is_homogeneous(s[i:j+1], k):
	            max_length = max(max_length, j - i + 1)
	return max_length

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public int characterReplacement(String s, int k) {
        HashMap<Character, Integer> freq = new HashMap<>(); // frequency map
        int l = 0;  // left pointer
        int maxCharCount = 0;  // max frequency of any char in window
        int ans = 0;  // result
        
        for (int r = 0; r < s.length(); r++) {  // right pointer
            char c = s.charAt(r);
            freq.put(c, freq.getOrDefault(c, 0) + 1);
            maxCharCount = Math.max(maxCharCount, freq.get(c));
            
            // Check if changes needed exceed k
            while ((r - l + 1) - maxCharCount > k) {
                char leftChar = s.charAt(l);
                freq.put(leftChar, freq.get(leftChar) - 1);
                l++;
            }
            
            ans = Math.max(ans, r - l + 1);
        }
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        freq: defaultdict = defaultdict(int)  # character frequency in window
        l: int = 0  # left pointer
        max_char_count: int = 0  # max frequency of any char in window
        ans: int = 0  # result
        
        for r in range(len(s)):  # right pointer
            freq[s[r]] += 1
            max_char_count = max(max_char_count, freq[s[r]])
            
            # Check if changes needed exceed k
            while (r - l + 1) - max_char_count > k:
                freq[s[l]] -= 1
                l += 1
            
            ans = max(ans, r - l + 1)
        
        return ans

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string s. The sliding window ensures that each character is processed only once.
  • 🧺 Space complexity: O(1) as we only store character frequencies for uppercase English letters (26).