Overview
This lecture explains how to solve the "Maximum Difference Between Even and Odd Frequency Two" problem (LeetCode 345) using an optimal sliding window and prefix sum approach.
Problem Statement & Constraints
- Given a string S of digits (0–4) and an integer K.
- Find a substring of length at least K where:
- Character A has an odd frequency,
- Character B has an even frequency,
- Maximize frequency difference: f(A) - f(B).
- Each substring may contain other characters; at least one valid substring is guaranteed.
- K ranges from 1 to S.length.
Variable-Size Sliding Window Approach
- Use two pointers (L, R) to define a window of size at least K.
- Window can expand/shrink but never below K.
- For each (A, B) pair (A ≠ B, 5 digits: 20 possible pairs), examine all valid substrings.
Pairing and Complexity Analysis
- 20 (A, B) pairs, process each in O(N).
- Total complexity: O(N × 20).
- Use prefix sum arrays for counting frequencies efficiently per window.
Prefix Sum & State Optimization
- For each A, B, build prefix sums tracking cumulative frequencies up to each index.
- Window frequency: freq in [L, R] = prefixSum[R+1] - prefixSum[L].
- For validity:
- f(A) in window must be odd,
- f(B) in window must be even,
- Both A and B must appear at least once.
Parity State Management
- Parity (even/odd) of prefix sum values controls valid window selection.
- Four possible (A, B) parity states: (even, even), (even, odd), (odd, even), (odd, odd).
- Use a min-value array (size 4) for each possible parity combination to track optimal L.
Validity & Optimality Checks
- Only consider windows where:
- f(A) is odd from L to R,
- f(B) is even from L to R,
- Both counts are positive.
- At each R, use min-value arrays to find optimal L efficiently in O(1).
Implementation Steps
- For each pair (A, B):
- Compute prefix sums for A and B.
- Initialize min-value and min-index arrays for parity states.
- For R = K–1 to N–1:
- Check and update max difference using parity states and min-value arrays.
- Update min-value/min-index for current L as R slides right.
Key Terms & Definitions
- Prefix Sum — Cumulative sum array for fast range queries.
- Sliding Window (Two-Pointer) — Technique to efficiently process all subarrays/substrings.
- Parity — Whether a count is even (0) or odd (1).
- State — Combination of parity for A and B (4 total).
- f(A), f(B) — Frequency of characters A and B in current window.
Action Items / Next Steps
- Practice implementing prefix sum and two-pointer sliding window.
- Review the code and dry run with sample inputs for full understanding.
- Optional: Solve "Range Sum Query Immutable" for more prefix sum practice.