🗓 Daily LeetCode Progress – Day 7

Problems Solved:

#567 Permutation in String
#424 Longest Repeating Character Replacement

This continues my daily series (Day X: Sliding Window patterns). Today I focused on two classic window-based substring problems: checking if a permutation exists inside another string, and extending the window with controlled replacements to maximize uniform substrings. Both are implemented in Python and C++.

💡 What I Learned

Today’s focus was on sliding window techniques with frequency tracking:

For Permutation in String, the key is to keep two frequency maps (need vs. window) and slide the window over s2, updating counts incrementally.
For Longest Repeating Character Replacement, the trick is to maintain the count of the most frequent character in the window, and shrink the window only when replacements exceed k.
Learned how frequency arrays (vector<int>) in C++ are faster than hash maps for fixed alphabet problems.
Practiced careful updates: adding new right character, removing old left character.

🧩 #567 — Permutation in String

Python (Counter-based sliding window)

from collections import Counter

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        n,m = len(s1), len(s2)
        if n > m:
            return False

        need = Counter(s1)
        window = Counter(s2[:n])

        if window == need:
            return True

        for i in range(n, m):
            add_char = s2[i]
            rem_char = s2[i-n]

            window[add_char] += 1
            window[rem_char] -= 1

            if window[rem_char] == 0:
                del window[rem_char]

            if window == need:
                return True
        return False

Why it works:
We maintain a sliding window of length len(s1) over s2. By comparing frequency counts at each step, we can detect if the window is a permutation of s1.

Time: O(n)
Space: O(26)

C++ (Frequency array sliding window)

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int n = s1.size(), m = s2.size();
        if (n > m) return false;

        vector<int> need(26, 0), window(26, 0);

        for (char c : s1) need[c - 'a']++;
        for (int i = 0; i < n; i++) window[s2[i] - 'a']++;

        if (window == need) return true;

        for (int i = n; i < m; i++) {
            window[s2[i] - 'a']++;
            window[s2[i-n] - 'a']--;
            if (window == need) return true;
        }
        return false;
    }
};

Why it works:
Instead of using maps, we leverage fixed-size arrays of length 26 for O(1) character updates and fast equality checks.

🧩 #424 — Longest Repeating Character Replacement

Python (Sliding window with max frequency)

from collections import defaultdict

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = defaultdict(int)
        left,max_freq,best = 0,0,0

        for right,ch in enumerate(s):
            count[ch] += 1
            max_freq = max(max_freq, count[ch])

            while (right - left + 1) - max_freq > k:
                count[s[left]] -= 1
                left += 1

            best = max(best, right - left + 1)
        return best

Why it works:
Keep track of the most frequent char count in the window. If replacements needed exceed k, shrink from the left. Otherwise, keep expanding.

Time: O(n)
Space: O(26)

C++ (Sliding window with max frequency)

class Solution {
public:
    int characterReplacement(string s, int k) {
        vector<int> freq(26, 0);
        int left = 0, best = 0, maxFreq = 0;

        for (int right = 0; right < (int)s.size(); ++right) {
            int r = s[right] - 'A';
            freq[r]++;
            maxFreq = max(maxFreq, freq[r]);

            while ((right - left + 1) - maxFreq > k) {
                freq[s[left] - 'A']--;
                left++;
            }

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

Why it works:
We allow at most k characters to be changed to the majority character in the window. By maintaining maxFreq, we avoid recomputation.

📸 Achievements

Permutation in String (Python & C++):

Longest Repeating Character Replacement (Python & C++):

📦 Complexity Recap

Permutation in String: O(n) time, O(1) space (26 alphabet)
Longest Repeating Character Replacement: O(n) time, O(1) space (26 alphabet)

📣 Join the Journey

I’m solving and documenting problems daily in both Python and C++, highlighting sliding window tricks and common pitfalls. Follow along if you’re into algorithms and optimization.

Links