🔢Beginner-Friendly Guide "Maximum Difference Between Even and Odd Frequency II" LeetCode 3445 (C++ | JavaScript | Python)

#programming #javascript #cpp #python

Hey, algorithm adventurers! 🔍✨

Today we’re diving into a tricky substring frequency problem from LeetCode — 3445: Maximum Difference Between Even and Odd Frequency II. This one mixes frequency parity, substring windows, and greedy insight. Let’s break it down and crack it open. 💡

📜 Problem Overview

Given a string s consisting of digits '0' to '4', and an integer k, your task is to find the maximum difference freq[a] - freq[b] in a substring of s of size at least k, where:

Character a has an odd frequency.
Character b has an even frequency.

You can pick any substring and any two characters (a ≠ b). If no such substring exists, return -1.

🧠 Intuition & Strategy

The challenge here is tracking character frequencies in valid substrings and comparing their parity — without scanning every substring (which is too slow).

Our optimized idea:

Iterate over all a ≠ b digit pairs (0 to 4).
Use prefix counts for a and b.
For each right pointer (right), slide the left pointer (left) to ensure the window size is at least k, and the window includes both a and b.
Use a clever bitmasking strategy to track frequency parity combinations.
Store the minimum prefix diff for each (parity_a, parity_b) and compute max difference greedily.

⚙️ C++ Code (Optimized)

class Solution {
public:
    int maxDifference(string s, int k) {
        auto getStatus = [](int cnt_a, int cnt_b) -> int {
            return ((cnt_a & 1) << 1) | (cnt_b & 1);
        };

        int n = s.size();
        int ans = INT_MIN;
        for (char a = '0'; a <= '4'; ++a) {
            for (char b = '0'; b <= '4'; ++b) {
                if (a == b) continue;
                int best[4] = {INT_MAX, INT_MAX, INT_MAX, INT_MAX};
                int cnt_a = 0, cnt_b = 0;
                int prev_a = 0, prev_b = 0;
                int left = -1;
                for (int right = 0; right < n; ++right) {
                    cnt_a += (s[right] == a);
                    cnt_b += (s[right] == b);
                    while (right - left >= k && cnt_b - prev_b >= 2) {
                        int status = getStatus(prev_a, prev_b);
                        best[status] = min(best[status], prev_a - prev_b);
                        ++left;
                        prev_a += (s[left] == a);
                        prev_b += (s[left] == b);
                    }
                    int status = getStatus(cnt_a, cnt_b);
                    if (best[status ^ 2] != INT_MAX) {
                        ans = max(ans, cnt_a - cnt_b - best[status ^ 2]);
                    }
                }
            }
        }
        return ans;
    }
};

🌐 JavaScript Version

var maxDifference = function(s, k) {
    const getStatus = (a, b) => ((a & 1) << 1) | (b & 1);
    let n = s.length, ans = -Infinity;

    for (let ca = 0; ca <= 4; ++ca) {
        for (let cb = 0; cb <= 4; ++cb) {
            if (ca === cb) continue;
            let best = Array(4).fill(Infinity);
            let cntA = 0, cntB = 0;
            let prevA = 0, prevB = 0;
            let left = -1;
            for (let right = 0; right < n; ++right) {
                cntA += s[right] === String(ca);
                cntB += s[right] === String(cb);
                while (right - left >= k && cntB - prevB >= 2) {
                    let status = getStatus(prevA, prevB);
                    best[status] = Math.min(best[status], prevA - prevB);
                    ++left;
                    prevA += s[left] === String(ca);
                    prevB += s[left] === String(cb);
                }
                let status = getStatus(cntA, cntB);
                if (best[status ^ 2] < Infinity) {
                    ans = Math.max(ans, cntA - cntB - best[status ^ 2]);
                }
            }
        }
    }
    return ans;
};

🐍 Python Version

def maxDifference(s: str, k: int) -> int:
    def get_status(a, b):
        return ((a & 1) << 1) | (b & 1)

    n = len(s)
    ans = float('-inf')

    for ca in range(5):
        for cb in range(5):
            if ca == cb:
                continue
            best = [float('inf')] * 4
            cnt_a = cnt_b = prev_a = prev_b = 0
            left = -1
            for right in range(n):
                cnt_a += s[right] == str(ca)
                cnt_b += s[right] == str(cb)
                while right - left >= k and cnt_b - prev_b >= 2:
                    status = get_status(prev_a, prev_b)
                    best[status] = min(best[status], prev_a - prev_b)
                    left += 1
                    prev_a += s[left] == str(ca)
                    prev_b += s[left] == str(cb)
                status = get_status(cnt_a, cnt_b)
                if best[status ^ 2] < float('inf'):
                    ans = max(ans, cnt_a - cnt_b - best[status ^ 2])

    return ans

🧪 Test Cases

Input: s = "1122211", k = 3
Output: 1

Input: s = "12233", k = 4
Output: -1

Input: s = "110", k = 3
Output: -1

Input: s = "000112233444", k = 5
Output: 2  (Depends on chosen characters)

⏱ Time & Space Complexity

Time Complexity: O(25 * n) = O(n) — because we only iterate fixed pairs of digits (0-4)
Space Complexity: O(1) — only fixed-sized counters and arrays used

✨ Wrap-Up

This problem elegantly blends parity logic, prefix optimizations, and windowed comparisons into one hard but rewarding problem. If you enjoy playing with frequencies and substring conditions, this one’s for you! 📊🧠

If this breakdown helped you understand or solve the problem, consider dropping a ❤️, saving it, and following for more!

Happy coding! 🚀