🔢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! 🚀

User Feedback & The Pivot That Saved The Project ↪️

We’re following the journey of a dev team building on the Stellar Network as they go from hackathon idea to funded startup, testing their product in the real world and adapting as they go.

Watch full video 🎥