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="abcababb", k=2
Output: 5
Explanation: Replace the two 'a' with 'b' in the substring 'ababb' to get the longest substring "bbbbb" with same letters.

Example 2:

1
2
3

Input: s="abccde", k=1
Output: 3
Explanation: Replace the 'b' or 'd' with 'c' to get the the longest substring "ccc" with same letters.

Solution

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.

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.

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).