[Solution]Problem 57:Longest Repeating Character with Replacement[Google]

I just made your weekends slightly more fun

Sep 23, 2022

To learn more about the newsletter, check our detailed About Page + FAQs

To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.

Recommend this publication to Substack over here

Take the next step by subscribing here

How did you do on this one? Let me know.

This problem can be found as problem 424. Longest Repeating Character Replacement on Leetcode.

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.

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.

Constraints:

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

You can test your solution here

Step 1: Understanding the Moving Parts

This is a question with a lot of different components. We have the string, the longest substring, and a k value. In such cases, I like to look at the problem and see how these all might be related to each other. This can help us spot the patterns and ideas to unravel the problem.

Let’s take a random substring containing multiple characters first. Is there anything we can do to get closer to the solution? One thing would be to figure out what the maximum possible length of our modified substring would be. How can we do that?

Logically, we want to know which char has the largest count. We want to keep that and replace the other characters using our budget of k. This is the only way we can possibly get the largest substring.

This leads to an important insight that will help us solve the problem- given a window for a substring, the biggest substring of repeating chars (after replacement) will be based on the character that shows up the most times. We’ll just flip the others to match this. Since we will need to know how many times we’ve seen the characters, our good pal Hash Map/Dictionary might end up being useful.

Technology Made Simple

Understanding Hashing [Math Mondays]

Happy Monday my lovely reader, I have something real special for you today. We are going to cover hashing. This is a very important idea that shows up in a lot of places. You know the most common application, in the amazing Dictionaries or Sets. Both these data structures use Hashing to ensure the constant time lookups and insertions. However, this idea…

3 years ago · 2 likes · Devansh

This leads us to a logical next step, how do we build the correct window?

Step 2: Building the Window

We’ve reduced the original problem to a slightly simpler problem- find the window where we can make the character replacements and get the max possible length. Let’s now see if we can figure out anything else to make further progress.

What is the smallest possible size of the window? Clearly, it will be 1 character. And we can set our window starting from the first character. It will expand/shift depending on our needs, but we now have a starting point. Now let’s look at the window shifting. As always, we will be relying on our old friend, case by case analysis to break down what happens after the start.

We want to expand our window- Our window will be expanded by moving a right pointer up by one. In such a case, we want to see how the new character changes the distribution of the number of characters in our window. After we do this, we have another consideration to make. If within our current window, we can change all the other characters to match the dominant character, then the maximum possible length for our window will be its length (computed as right-left+1). If we can’t flip all the less-common characters, we move on to case 2.
We shift our window- If we hit the case where we can’t flip the characters, we want to shift our window to a better one. How do we do that? Simply shift the left pointer by one. However, keep in mind that we’re changing the characters in our window. So we want to update our charsSeen dict accordingly.

To learn more about Case by Case Analysis, read our technique Tuesday on it.

Technology Made Simple

Solving Coding Problems through Case by Case Analysis of Input[Technique Tuesdays]

Hello hello, Today I will share with you a deceptively powerful technique to really boost your problem-solving. It’s one of those techniques that are extremely simple, so they often blend into the background. Nevertheless, without this technique, I would have a hard time coming up with solutions in a clear and efficient way…

3 years ago · 2 likes · Devansh

Okay, seems like we have a good idea of how to proceed. Now that we have done the skeleton, let’s do the coding to tie up all the ends.

Step 3: Coding it Up

Most of the coding is relatively simple. It’s about putting the pieces together. Especially if you’ve solved similar problems. One of the reasons I picked this problem was because it really tests your problem-solving ability, without really making the coding part too difficult. I think more questions should be like this because this is more natural to your coding journey. The code for this problem can be found below-

def characterReplacement(self, s: str, k: int) -> int:
        
        left = 0
        charsSeen = {}
        maxCharCount = 0
        result = 0
        
        for right,c in enumerate(s):
            if c not in charsSeen:
                charsSeen[c]=1
            else:
                charsSeen[c]+=1
            
            if charsSeen[c]>=maxCharCount: # we have a new maximum #occuring char
                maxCharCount = charsSeen[c]
            
            if (right-left+1-maxCharCount)<=k:#we can make flips
                result = max(result,right-left+1)
            
            else:
                charsSeen[s[left]]-=1 #we can't flip, move the window
                left+=1
        
        return result

You will notice this part of the sliding window pattern. I could have jumped into this problem having said that, and you could more directly solve the problem in your interview if you did say that. However, the way I built up to this would only need you to speak for 5 mins more (at most). And you’ll be able to show off your communication and step-step methodical problem-solving approach. And these are a lot more attractive. If you’re looking to build your ability with Sliding Window problems, go over the other solutions in the archive. I would suggest this one in particular, which is a fav of Meta.

Time Complexity- O(N).

Space Complexity- O(1). Worst case, our dict stores the 26 letters. So we have constant time space usage.

Loved the solution? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.