Longest Repeating Character Replacement

Med

#0411Time: O(N^2), where N is the length of the string `s`. The outer loop runs N times, and the inner loop runs up to N times. Inside the inner loop, operations are constant time.Space: O(1), as the frequency map `charCounts` has a fixed size of 26, which is constant.10 companies

Patterns

Sliding Window

Data structures

Hash Table String

Companies

ByteDance Flipkart Yandex Turing

Prompt

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

Constraints:

1 <= s.length <= 10⁵
s consists of only uppercase English letters.
0 <= k <= s.length

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through all possible substrings of the input string s. For each substring, it calculates the minimum number of replacements required to make all characters in it the same. If this number is within the allowed limit k, the length of the substring is considered as a potential answer. The maximum length found among all valid substrings is the result.

Algorithm

Initialize maxLength = 0.
Iterate through the string with a starting pointer i from 0 to n-1.
For each i, start an inner loop with an ending pointer j from i to n-1.
Maintain a frequency map (e.g., an array of size 26) for the characters in the substring s[i..j].
In the inner loop, as j increments, update the frequency of s[j].
Find the frequency of the most common character in the current substring s[i..j], let's call it maxFreq.
The number of replacements needed is (j - i + 1) - maxFreq.
If (j - i + 1) - maxFreq <= k, then this substring is a candidate. Update maxLength = max(maxLength, j - i + 1).
After both loops complete, maxLength will hold the answer.

Walkthrough

The naive brute-force approach would be to check every substring and for each substring, check against all 26 possible characters, leading to an O(n^3) complexity. We can optimize this.

A better brute-force method involves iterating through all possible start and end points of a substring, which is O(n^2). For each substring, we can determine the number of replacements needed more efficiently.

The number of replacements for a substring is its length minus the frequency of its most common character. To find this, we can maintain a frequency map for the characters within the current substring.

As we extend the substring by one character (by moving the end pointer), we update the frequency map and find the new most frequent character. This check takes constant time (O(1) since there are only 26 uppercase letters).

1class Solution {2    public int characterReplacement(String s, int k) {3        int n = s.length();4        int maxLength = 0;5        for (int i = 0; i < n; i++) {6            int[] charCounts = new int[26];7            int maxFreq = 0;8            for (int j = i; j < n; j++) {9                charCounts[s.charAt(j) - 'A']++;10                maxFreq = Math.max(maxFreq, charCounts[s.charAt(j) - 'A']);11                int replacementsNeeded = (j - i + 1) - maxFreq;12                if (replacementsNeeded <= k) {13                    maxLength = Math.max(maxLength, j - i + 1);14                }15            }16        }17        return maxLength;18    }19}

Complexity

Time

O(N^2), where N is the length of the string `s`. The outer loop runs N times, and the inner loop runs up to N times. Inside the inner loop, operations are constant time.

Space

O(1), as the frequency map `charCounts` has a fixed size of 26, which is constant.

Trade-offs

Pros

Simple to understand and implement.
It's a direct translation of the problem statement.

Cons

Inefficient for large inputs. It will result in a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints (N up to 10^5).

A much more efficient approach uses the sliding window technique. We maintain a 'window' (a substring) and expand it to the right. We keep track of the character frequencies within the window. If the window becomes 'invalid' (meaning it requires more than k replacements), we shrink it from the left until it's valid again. The maximum size the window reaches at any point is the answer.

Algorithm

Initialize left = 0, maxLength = 0, maxFreq = 0, and a frequency map counts (array of size 26).
Iterate through the string with a pointer right from 0 to n-1.
Increment the count for s[right] in the counts map.
Update maxFreq = max(maxFreq, count of s[right]).
Check if the current window is invalid: (right - left + 1) - maxFreq > k.
If it is invalid, shrink the window from the left: decrement the count of s[left] and increment left.
The window size right - left + 1 is always the size of the current valid (or just-became-valid) window. The maximum size this window ever reaches is the answer. We update maxLength = max(maxLength, right - left + 1) in each iteration.
Return maxLength.

Walkthrough

The core idea is to find the longest substring (window) s[left..right] where the number of characters that are not the most frequent character is at most k.

This condition can be expressed as: (window_length) - (frequency_of_most_common_char) <= k.

We use two pointers, left and right, to define the current window. We iterate right from the beginning to the end of the string, expanding the window.

For each expansion, we update the frequency count of the new character s[right] and also keep track of maxFreq, the highest frequency of any single character seen so far in the window.

After expanding, we check if our window is valid using the condition (right - left + 1) - maxFreq <= k. If it's not (> k), it means we have too many characters that need replacement. To fix this, we must shrink the window by moving the left pointer to the right and decrementing the count of the character s[left].

A key optimization is that we don't need to re-calculate maxFreq when we shrink the window. We are looking for the longest substring. The window size only increases when right moves, not when left moves. So, we can maintain the historical maxFreq and the window will only expand again when we find a new, longer valid substring (which might happen because maxFreq increases).

The length of the window right - left + 1 is a candidate for the answer at each step, and we keep track of the maximum length seen.

1class Solution {2    public int characterReplacement(String s, int k) {3        int n = s.length();4        int[] charCounts = new int[26];5        int left = 0;6        int maxLength = 0;7        int maxFreq = 0;8 9        for (int right = 0; right < n; right++) {10            // Expand the window11            charCounts[s.charAt(right) - 'A']++;12            maxFreq = Math.max(maxFreq, charCounts[s.charAt(right) - 'A']);13 14            // Check if the window is valid15            // Number of characters to replace = windowLength - maxFreq16            int windowLength = right - left + 1;17            if (windowLength - maxFreq > k) {18                // Shrink the window from the left19                charCounts[s.charAt(left) - 'A']--;20                left++;21            }22 23            // The window size is a potential answer24            maxLength = Math.max(maxLength, right - left + 1);25        }26        return maxLength;27    }28}

Complexity

Time

O(N), where N is the length of the string `s`. Both `right` and `left` pointers traverse the string at most once. The work inside the loop is constant time.

Space

O(1), as the frequency map `charCounts` has a fixed size of 26, which is constant regardless of the input string size.

Trade-offs

Pros

Highly efficient with linear time complexity.
Optimal solution for this problem.
Effectively utilizes the properties of the problem to avoid redundant calculations.

Cons

The logic, especially the part about not needing to update maxFreq when shrinking the window, can be slightly non-intuitive at first glance.

Solutions

Solution

1class Solution { public int characterReplacement ( String s , int k ) { int [] counter = new int [ 26 ]; int i = 0 ; int j = 0 ; for ( int maxCnt = 0 ; i < s . length (); ++ i ) { char c = s . charAt ( i ); ++ counter [ c - 'A' ]; maxCnt = Math . max ( maxCnt , counter [ c - 'A' ]); if ( i - j + 1 - maxCnt > k ) { -- counter [ s . charAt ( j ) - 'A' ]; ++ j ; } } return i - j ; } }

1class Solution { public: int characterReplacement ( string s , int k ) { vector < int > counter ( 26 ); int i = 0 , j = 0 , maxCnt = 0 ; for ( char & c : s ) { ++ counter [ c - 'A' ]; maxCnt = max ( maxCnt , counter [ c - 'A' ]); if ( i - j + 1 > maxCnt + k ) { -- counter [ s [ j ] - 'A' ]; ++ j ; } ++ i ; } return i - j ; } };

1class Solution : def characterReplacement ( self , s : str , k : int ) -> int : counter = [ 0 ] * 26 i = j = maxCnt = 0 while i < len ( s ): counter [ ord ( s [ i ]) - ord ( 'A' )] += 1 maxCnt = max ( maxCnt , counter [ ord ( s [ i ]) - ord ( 'A' )]) if i - j + 1 > maxCnt + k : counter [ ord ( s [ j ]) - ord ( 'A' )] -= 1 j += 1 i += 1 return i - j

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem