Coding

Longest Repeating Character Replacement

Asked at

InfoEdge India Ltd

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an integer k and a string s, any character in the string can be selected and changed to any other uppercase English character. This operation can be performed up to** k **times. After completing these steps, return the length of the longest substring that contains the same letter.

Input : s = "BAABAABBBAAA" , k = 2 Output : 6 Explanation : we can change the B present at index 0 , 3 (0 base indexing) to A. The new string is "AAAAAABBBAAA". The substring "AAAAAA" is the longest substring having same letter with length 6.

Input : s = "AABABBA" , k = 1 Output : 4 Explanation : The underlined characters are changed in the new string obtained. The new string is "AABBBBA". The substring "BBBB" is the answer. There are other ways to achieve this answer.

Input : s = "ABCDEF" k = 1

1 <= s.length <= 105
0 <= k <= s.length
s contains only English uppercase letters.

cpp

class Solution {
public:
    int characterReplacement(string s, int k) {
        //your code goes here
    }
};

java

class Solution {
    public int characterReplacement(String s, int k) {
        //your code goes here
    }
}

python

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        #your code goes here

javascript

class Solution {
    characterReplacement(s, k) {
        //your code goes here
    }
}

csharp

public class Solution
{
    public int CharacterReplacement(string s, int k)
    {
        //your code goes here
    }
}

func characterReplacement(s string, k int) int {

}

Stuck? Show a way to structure it+

01Expand the right boundary and update its frequency.
02Track the highest frequency seen in the window.
03Shrink while window length minus that frequency exceeds k.
04Record the maximum valid length.
05Use a fixed alphabet count array.

Reference answer

Maintain a window and counts for its uppercase letters. After adding the right character, update maxFreq, the largest count seen for any letter in the window. The window can become one repeated character using windowLength minus maxFreq replacements, so shrink from the left while that value exceeds k. Update the best length after restoring feasibility. It is safe not to decrease maxFreq when shrinking: it may be stale and make the window temporarily look more feasible, but it never causes the maximum answer to be too large because an earlier window achieved that frequency; this standard optimization keeps the scan linear. With a 26-letter alphabet, time is O(n) and space is O(1). Explain the invariant aloud rather than saying the algorithm merely tries every substring.

Then expect these follow-ups

Why is a stale maxFreq still correct here?
Tests: correctness reasoning
How would this change for an arbitrary Unicode alphabet?
Tests: implementation extension

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question