Problem Informations

• Problem Index: 424
• Problem Link: Longest Repeating Character Replacement
• Topics: Hash Table, String, Sliding Window

Problem Description

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.

Example 1:

Input: s = “ABAB”, k = 2
Output: 4
Explanation: Replace the two ‘A’s with two ‘B’s or vice versa.

Example 2:

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 exist other ways to achieve this answer too.

Constraints:

• $1 \leq s.length \leq 10^5$
• $s$ consists of only uppercase English letters.
• $0 \leq k \leq s.length$

Intuition

The problem revolves around maximizing the length of a substring made up of the same character, allowing for up to $k$ modifications of the string. The key insight is to leverage a sliding window approach combined with frequency counting, where the window dynamically adjusts to maintain feasibility with respect to the allowable modifications. This allows us to efficiently explore potential solutions across the string while maintaining constraints.

Approach

The approach utilizes a sliding window technique with two pointers, left and right, to define the current window of interest within the string. As right traverses the string, the frequency of each character within the window is tracked using a fixed-size vector charCount of length 26 (to represent each uppercase English letter).

1. Initialization:

   • Initialize left and right pointers to the start of the string.
   • Initialize maxLength to 0 to store the maximum length of a valid substring found.
   • Initialize charCount vector to keep track of the frequency of each character within the current window.

2. Sliding Window Expansion:

   • Incrementally increase the right pointer to expand the window.
   • Update the corresponding character count in charCount for the char at right.

3. Validity Check:

   • For the current window ranging from left to right, calculate the number of changes required to make all characters the same. This is given by right - left + 1 - max_count, where max_count is the frequency of the most common character in the current window.
   • If the number of changes required exceeds $k$, increment the left pointer to shrink the window from the left until the window becomes valid again. Adjust the character frequency for the character at the left as it is no longer in the window.

4. Update Result:

   • Compute the length of the current valid window (right - left + 1) and update maxLength accordingly if this window is larger.

5. Termination:

   • When right has traversed the entire string, maxLength holds the length of the longest valid substring.

This algorithm efficiently computes the solution in linear time $O(n)$, where $n$ is the length of the string, leveraging both the sliding window method and character frequency counting.

Code

C++

class Solution {
public:
    int characterReplacement(string s, int k) {
        // Vector to count occurrences of each character
        vector<int> charCount(26, 0);
        
        int left = 0, right = 0;
        int maxLength = 0;

        // Slide the window with 'right' pointer
        for (; right < s.size(); right++) {
            // Update count for the current character
            charCount[s[right] - 'A']++;

            // Check if current window is valid        
            while (right - left + 1 - *max_element(charCount.begin(), charCount.end()) > k) {
                // If not valid, shrink window from left
                charCount[s[left] - 'A']--;
                left++;
            }

            // Update the maximum length found so far
            maxLength = max(maxLength, right - left + 1);
        }

        return maxLength;
    }
};

Python

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        # List to count occurrences of each character
        charCount = [0] * 26
        
        left = 0
        right = 0
        maxLength = 0

        # Slide the window with 'right' pointer
        while right < len(s):
            # Update count for the current character
            charCount[ord(s[right]) - ord('A')] += 1

            # Check if current window is valid        
            while right - left + 1 - max(charCount) > k:
                # If not valid, shrink window from left
                charCount[ord(s[left]) - ord('A')] -= 1
                left += 1

            # Update the maximum length found so far
            maxLength = max(maxLength, right - left + 1)
            right += 1

        return maxLength

Complexity

• Time complexity: $O(n)$

  The algorithm operates with a sliding window approach, where both the left and right pointers traverse the string $s$, stopping at each character once. The operations inside the loop, which include counting the characters and checking the maximum element in the fixed-size vector (size 26, corresponding to the number of uppercase English letters), take constant time $O(1)$. Therefore, the overall time complexity is linear, $O(n)$, where $n$ is the length of the string $s$.

• Space complexity: $O(1)$

  The space used by the algorithm is constant, $O(1)$, as it involves a fixed-size vector of size 26 to store character counts, regardless of the input size $n$. The additional variables like integers for the pointers and maximum length also use a fixed amount of space that does not grow with the input.