424. Longest repeating char replacement

#include <string.h>

int characterReplacement(char *s, int k) {
    int reps[26] = {0};
    int left = 0;
    int maxLen = k;
    int maxFreq = 0;
    int len = strlen(s);

    for (int right = 0; right < len; right++) {
        int c = s[right] - 'A';
        reps[c]++;

        if (reps[c] > maxFreq) {
            maxFreq = reps[c];
        }

        if (right - left - maxFreq >= k) {
            reps[s[left] - 'A']--;
            left++;
        }

        if (right - left + 1 > maxLen) {
            maxLen = right - left + 1;
        }
    }

    return maxLen;
}

#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
  int characterReplacement(string s, int k) {
    unordered_map<char, int> reps; // reps of a char in current window
    int left = 0;
    int maxLen = k;
    int maxFreq = 0;

    for (int right = 0; right < s.size(); right++) {
      reps[s[right]]++;
      maxFreq = max(maxFreq, reps[s[right]]);

      if (right - left - maxFreq >= k) {
        reps[s[left]]--;
        left++;
      }

      maxLen = max(maxLen, right - left + 1);
    }

    return maxLen;
  }
};

// maxFreq never decreases, so the window can stay invalid for a while without
// changing the answer: every length it reaches has some valid window of that
// length. Full argument and trace in
// 00_docs/04_sliding_window/4b_variable_size.md (Longest Repeating Character Replacement).

package main

func characterReplacement(s string, k int) int {
    reps := make(map[byte]int)
    left := 0
    maxLen := k
    maxFreq := 0

    for right := 0; right < len(s); right++ {
        c := s[right]
        reps[c]++
        if reps[c] > maxFreq {
            maxFreq = reps[c]
        }

        if right-left-maxFreq >= k {
            reps[s[left]]--
            left++
        }

        if length := right - left + 1; length > maxLen {
            maxLen = length
        }
    }

    return maxLen
}

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int characterReplacement(String s, int k) {
        Map<Character, Integer> reps = new HashMap<>();
        int left = 0;
        int maxLen = k;
        int maxFreq = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            reps.put(c, reps.getOrDefault(c, 0) + 1);
            maxFreq = Math.max(maxFreq, reps.get(c));

            if (right - left - maxFreq >= k) {
                char leftChar = s.charAt(left);
                reps.put(leftChar, reps.get(leftChar) - 1);
                left++;
            }

            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}

class Solution {
  characterReplacement(s, k) {
    const reps = new Map();
    let left = 0;
    let maxLen = k;
    let maxFreq = 0;

    for (let right = 0; right < s.length; right++) {
      const c = s[right];
      reps.set(c, (reps.get(c) || 0) + 1);
      maxFreq = Math.max(maxFreq, reps.get(c));

      if (right - left - maxFreq >= k) {
        const leftChar = s[left];
        reps.set(leftChar, reps.get(leftChar) - 1);
        left++;
      }

      maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
  }
}

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        reps = {}
        left = 0
        max_len = k
        max_freq = 0

        for right, c in enumerate(s):
            reps[c] = reps.get(c, 0) + 1
            max_freq = max(max_freq, reps[c])

            if right - left - max_freq >= k:
                reps[s[left]] -= 1
                left += 1

            max_len = max(max_len, right - left + 1)

        return max_len

use std::collections::HashMap;

struct Solution;

impl Solution {
    fn character_replacement(s: String, k: i32) -> i32 {
        let bytes = s.as_bytes();
        let mut reps: HashMap<u8, i32> = HashMap::new();
        let mut left: i32 = 0;
        let mut max_len = k;
        let mut max_freq = 0;

        for right in 0..bytes.len() {
            let c = bytes[right];
            let count = reps.entry(c).or_insert(0);
            *count += 1;
            max_freq = max_freq.max(*count);

            if right as i32 - left - max_freq >= k {
                *reps.get_mut(&bytes[left as usize]).unwrap() -= 1;
                left += 1;
            }

            max_len = max_len.max(right as i32 - left + 1);
        }

        max_len
    }
}