Maximum Difference Between Even and Odd Frequency II - Video Solutions

Problem Overview: Given a string, you need the maximum difference between the frequency of a character with odd count and another character with even count inside a valid substring. The challenge is enforcing the parity constraints while scanning substrings efficiently without checking every possible range.

Approach 1: Brute Force Substring Enumeration (O(n^3) time, O(1) space)

Generate every possible substring and compute the frequency of characters inside it. For each substring, check all character pairs and compute oddFreq - evenFreq when one frequency is odd and the other is even. Frequency counting requires scanning the substring or maintaining counts, and checking pairs adds another loop. This approach works only for very small inputs because substring enumeration already costs O(n^2), and verifying frequency conditions pushes the complexity close to O(n^3).

Approach 2: Prefix Frequency + Pair Enumeration (O(26^2 · n) time, O(26 · n) space)

Instead of recomputing counts for every substring, precompute prefix frequency arrays. With prefix sums, the count of any character in a substring can be obtained in O(1). Then enumerate ordered character pairs (a, b) where a represents the odd-frequency candidate and b the even-frequency candidate. For each pair, iterate through the string and derive counts using prefix differences. This reduces repeated counting but still requires scanning the string for every pair.

Approach 3: Character Pair Enumeration + Sliding Window + Prefix State Compression (O(26^2 · n) time, O(n) space)

The optimized solution fixes a pair of characters (a, b) and scans the string once using prefix differences and parity states. Maintain running counts for both characters and track whether their frequencies are odd or even. A compressed prefix state represents the parity combination seen so far. Using a technique similar to prefix sums with state tracking, you store the minimum prefix difference for each parity state and update the answer while expanding the window. This effectively converts the substring constraint into a difference of prefix states.

Enumeration over all character pairs ensures every valid odd/even combination is considered, while the linear scan ensures each pair is processed in O(n). The approach relies on ideas from sliding window, prefix sum, and enumeration to avoid explicit substring generation.

Recommended for interviews: The character pair enumeration with sliding window and prefix state compression is the expected solution. Mentioning the brute force first shows you understand the search space. Transitioning to prefix differences and parity states demonstrates the optimization interviewers look for in hard string problems.