You are given a string s and an integer k. Your task is to find the maximum difference between the frequency of two characters, freq[a] - freq[b], in a substring subs of s, such that:
subs has a size of at least k.a has an odd frequency in subs.b has a non-zero even frequency in subs.Return the maximum difference.
Note that subs can contain more than 2 distinct characters.
Example 1:
Input: s = "12233", k = 4
Output: -1
Explanation:
For the substring "12233", the frequency of '1' is 1 and the frequency of '3' is 2. The difference is 1 - 2 = -1.
Example 2:
Input: s = "1122211", k = 3
Output: 1
Explanation:
For the substring "11222", the frequency of '2' is 3 and the frequency of '1' is 2. The difference is 3 - 2 = 1.
Example 3:
Input: s = "110", k = 3
Output: -1
Constraints:
3 <= s.length <= 3 * 104s consists only of digits '0' to '4'.1 <= k <= s.lengthProblem 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.
We want to find a substring subs of string s that satisfies the following conditions:
subs is at least k.a in subs is odd.b in subs is even.f_a - f_b, where f_a and f_b are the number of occurrences of a and b in subs, respectively.The characters in s are from '0' to '4', so there are 5 possible characters. We can enumerate all different character pairs (a, b), for a total of at most 5 times 4 = 20 combinations. We define:
a is the target character with odd frequency.b is the target character with even frequency.We use a sliding window to maintain the left and right boundaries of the substring, with variables:
l denotes the position before the left boundary, so the window is [l+1, r];r is the right boundary, traversing the entire string;curA and curB denote the number of occurrences of a and b in the current window;preA and preB denote the cumulative occurrences of a and b before the left boundary l.We use a 2D array t[2][2] to record the minimum value of preA - preB for each possible parity combination of the window's left end, where t[i][j] means preA bmod 2 = i and preB bmod 2 = j.
Each time we move r to the right, if the window length satisfies r - l \ge k and curB - preB \ge 2, we try to move the left boundary l to shrink the window, and update the corresponding t[preA bmod 2][preB bmod 2].
Then, we try to update the answer:
$
ans = max(ans,\ curA - curB - t[(curA bmod 2) \oplus 1][curB bmod 2])
In this way, we can compute the maximum frequency difference for the current window each time r moves to the right.
The time complexity is O(n times |\Sigma|^2), where n is the length of s and |\Sigma| is the alphabet size (5 in this problem). The space complexity is O(1)$.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Enumeration | O(n^3) | O(1) | Educational baseline to understand the problem constraints and parity checks |
| Prefix Frequency + Pair Enumeration | O(26^2 · n) | O(26 · n) | When you want faster substring frequency queries using prefix sums |
| Pair Enumeration + Sliding Window + Prefix State Compression | O(26^2 · n) | O(n) | Optimal approach for large inputs; combines prefix difference tracking with parity states |
Maximum Difference Between Even and Odd Frequency II | Super Detailed | Leetcode 3445 | MIK • codestorywithMIK • 11,961 views views
Watch 9 more video solutions →Practice Maximum Difference Between Even and Odd Frequency II with our built-in code editor and test cases.
Practice on FleetCode