Bug Report for longest-repeating-substring-with-replacement

[KhoreyCh]

Bug Report for https://neetcode.io/problems/longest-repeating-substring-with-replacement

Please describe the bug below and include any steps to reproduce the bug or screenshots if possible.

This isn't so much a bug, it's more like an incomplete test. I was going through the lessons and was doing the longest repeating substring with replacement one, which appeared on leetcode.com

So when I did it on neetcode.com, I got full credit and passed all the test cases, but there was one edge case where my code failed that didn't appear on neetcode. So in the video you talked about how there was a way to solve it not in O(26n) time but instead in just O(n) by just keeping track of the largest amount of occurences of the most common characters.

When I was doing it (before watching your video on the solution) I was able to intuit that we wouldn't need to check the hashmap all 26 times, but I wasn't able to figure out that I could just keep track of the largest freq. I instead updated my most common character occurences after each iteration of "decreasing the window size" by just looking at the character that was getting "chopped off by the window shrinking" and setting my max between the character that was next on the chopping block, the character I just chopped off, and the character I just added to the window.

This is obviously close but not quite right, and on leetcode, it fails 1 test case, but on neetcode that test case doesn't appear, but I think it may be worth including.

The test case was s="AAAAABBBBCBB"
and here's my code below that passes everything except this test case above:

class Solution:

def characterReplacement(self, s: str, k: int) -> int:
    curMax=1
    Max=1
    maxCharCount=1
    maxChar=s[0]
    seenChar=defaultdict(int)
    seenChar[s[0]]+=1
    for i in range(1,len(s)):
        seenChar[s[i]]+=1
        curMax+=1
        if seenChar[s[i]]>=seenChar[maxChar]:
            maxChar=s[i]
            maxCharCount=seenChar[maxChar]
        while curMax-maxCharCount>k:
            seenChar[s[i-curMax+1]]-=1
            maxCharCount=max(seenChar[s[i-curMax+1]],seenChar[s[i]],seenChar[s[i-curMax+2]])
            curMax-=1
        Max=max(Max,curMax)
    return Max