LC424. Longest Repeating Character Replacement

Approach 1: Sliding Window

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        counts = defaultdict(int)
        res = 0
 
        l = 0
        for r in range(len(s)):
            counts[s[r]] += 1
 
            while (r - l + 1) - max(counts.values()) > k:
                counts[s[l]] -= 1
                l += 1
            
            res = max(res, r - l + 1)
 
        return res

Complexity

Time: $O(26\cdot n)\approx O(n)$
Space: $O(1)$

Approach 2: Sliding Window Optimized

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        counts = defaultdict(int)
        res = 0
 
        l = 0
        maxf = 0
        for r in range(len(s)):
            counts[s[r]] += 1
            maxf = max(maxf, counts[s[r]])
 
            # We don't have to keep updating the maxf since
            # it won't affect the final result. Yes, technically,
            # this looks wrong, but by keeping maxf the same, we
            # ensure res will only be as high as it was earlier until
            # we get a new maxf.
            while (r - l + 1) - maxf > k:
                counts[s[l]] -= 1
                l += 1
            
            res = max(res, r - l + 1)
 
        return res
            

Complexity

Time: $O(n)$
Space: $O(1)$

Notes

Other Languages

Swift

class Solution {
    func characterReplacement(_ s: String, _ k: Int) -> Int {
        var counts: [Character:Int] = [:]
        var res = 0
        let s = Array(s)
 
        var maxf = 0
        var l = 0
        for r in 0..<s.count {
            counts[s[r], default: 0] += 1
            maxf = max(maxf, counts[s[r]]!)
 
            while (r - l + 1) - maxf > k {
                counts[s[l]]! -= 1
                l += 1
            }
 
            res = max(res, r - l + 1)
        }
 
        return res
    }
}