Maximum Difference Between Even and Odd Frequency II
HardPrompt
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:
subshas a size of at leastk.- Character
ahas an odd frequency insubs. - Character
bhas a non-zero even frequency insubs.
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 * 104sconsists only of digits'0'to'4'.- The input is generated that at least one substring has a character with an even frequency and a character with an odd frequency.
1 <= k <= s.length
Approaches
3 approaches with complexity analysis and trade-offs.
The brute-force approach is the most straightforward way to solve the problem. It involves systematically checking every possible substring of the input string s, verifying if it meets the given criteria, and then calculating the potential difference to update a global maximum.
Algorithm
- Use three nested loops to generate all substrings and calculate their character frequencies.
- The outer loop
iiterates from0ton-1for the start of the substring. - The second loop
jiterates fromiton-1for the end of the substring. - Check if the substring length
j - i + 1is at leastk. - If the length is valid, a third loop
lfromitojcalculates the frequency of each character ('0' through '4') in the substrings[i...j]. - After calculating frequencies, iterate through all possible pairs of characters
(a, b). - If
freq[a]is odd andfreq[b]is non-zero and even, calculate the differencefreq[a] - freq[b]. - Keep track of the maximum difference found across all valid substrings and character pairs.
Walkthrough
This method iterates through all possible start and end indices, i and j, to define a substring. For each substring, it first checks if its length is at least k. If it is, the algorithm then computes the frequency of each character within that specific substring. This is done by iterating through the substring's characters and using an array to store counts. Once the frequencies are known, it searches for a character a with an odd frequency and a character b with a non-zero, even frequency. For every such valid pair (a, b), it calculates freq[a] - freq[b] and updates the overall maximum difference found so far. This process is repeated for all substrings of length k or more.
class Solution { public int maxDiff(String s, int k) { int n = s.length(); int maxDifference = Integer.MIN_VALUE; boolean found = false; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (j - i + 1 < k) { continue; } int[] freq = new int[5]; for (int l = i; l <= j; l++) { freq[s.charAt(l) - '0']++; } int maxOddFreq = -1; int minEvenFreq = Integer.MAX_VALUE; boolean hasOdd = false; boolean hasEven = false; for (int charIdx = 0; charIdx < 5; charIdx++) { if (freq[charIdx] > 0) { if (freq[charIdx] % 2 != 0) { maxOddFreq = Math.max(maxOddFreq, freq[charIdx]); hasOdd = true; } else { // non-zero and even minEvenFreq = Math.min(minEvenFreq, freq[charIdx]); hasEven = true; } } } if (hasOdd && hasEven) { maxDifference = Math.max(maxDifference, maxOddFreq - minEvenFreq); found = true; } } } // The problem guarantees a solution exists, but for robustness: return found ? maxDifference : 0; }}Complexity
Time
O(N³), where N is the length of the string. There are O(N²) substrings, and for each, we iterate up to N times to calculate frequencies. This is too slow for the given constraints.
Space
O(1), as the frequency map size is constant (5 for digits '0'-'4').
Trade-offs
Pros
Simple to understand and implement.
Cons
Extremely inefficient due to its cubic time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error on platforms with typical time limits for the given constraints.
This approach improves upon the naive brute-force method by optimizing the frequency calculation. Instead of re-calculating frequencies for each substring from scratch, it maintains a running count of character frequencies as the substring's endpoint expands.
Algorithm
- Use two nested loops. The outer loop
ifixes the start of the substring. - The inner loop
jextends the end of the substring fromiton-1. - For a fixed
i, maintain a frequency map for the current substrings[i...j]. - As
jincrements, update the frequency map in O(1) time by just incrementing the count for the new characters[j]. - For each substring
s[i...j]of length at leastk, iterate through all pairs of characters(a, b). - Check if
freq[a]is odd andfreq[b]is non-zero and even. - If the conditions are met, update the global maximum difference with
freq[a] - freq[b].
Walkthrough
We iterate through all possible starting positions i of a substring. For each i, we start building a substring by iterating a second pointer j from i to the end of the string. We use a frequency array to keep track of character counts for the substring s[i...j]. When we move from j to j+1, we simply increment the count for s.charAt(j+1). This avoids the third loop for frequency calculation, reducing the work done for each substring. After updating the frequencies for s[i...j], if its length is at least k, we check the conditions for all character pairs and update the maximum difference accordingly.
class Solution { public int maxDiff(String s, int k) { int n = s.length(); int maxDifference = Integer.MIN_VALUE; boolean found = false; for (int i = 0; i < n; i++) { int[] freq = new int[5]; for (int j = i; j < n; j++) { freq[s.charAt(j) - '0']++; if (j - i + 1 < k) { continue; } int maxOddFreq = -1; int minEvenFreq = Integer.MAX_VALUE; boolean hasOdd = false; boolean hasEven = false; for (int charIdx = 0; charIdx < 5; charIdx++) { if (freq[charIdx] > 0) { if (freq[charIdx] % 2 != 0) { maxOddFreq = Math.max(maxOddFreq, freq[charIdx]); hasOdd = true; } else { // non-zero and even minEvenFreq = Math.min(minEvenFreq, freq[charIdx]); hasEven = true; } } } if (hasOdd && hasEven) { maxDifference = Math.max(maxDifference, maxOddFreq - minEvenFreq); found = true; } } } return found ? maxDifference : 0; }}Complexity
Time
O(N²). Two nested loops run, and the work inside the inner loop is constant time (since the alphabet size is constant). For N up to 3 * 10⁴, N² is too large.
Space
O(1), as the frequency map size is constant.
Trade-offs
Pros
More efficient than the naive O(N³) approach.
Still relatively simple to implement.
Cons
Still too slow for the given constraints, leading to a 'Time Limit Exceeded' error.
This efficient approach reformulates the problem using prefix sums and focuses on optimizing the search for the best substring for each fixed pair of characters (a, b). By using a sliding window-like mechanism combined with state tracking based on count parities, it achieves a linear time complexity.
Algorithm
- The main idea is to fix the characters
aandband then find the optimal substring in O(N) time. This process is repeated for all5 * 4 = 20pairs of(a, b). - Precompute prefix sums
count[c][i]for each charactercup to indexi. - The difference
freq(a) - freq(b)for a substrings[p+1...j]can be written as(count[a][j] - count[b][j]) - (count[a][p] - count[b][p]). - We iterate
jfrom0ton-1. For eachj, we need to find an indexp <= j-kthat minimizescount[a][p] - count[b][p]subject to parity constraints. - The parity constraints are:
freq(a)is odd, meaningcount[a][j]andcount[a][p]have different parities.freq(b)is even, meaningcount[b][j]andcount[b][p]have the same parity. - The non-zero constraint for
freq(b)meanscount[b][j] != count[b][p]. - To handle this, we maintain two tables,
min1andmin2, for each of the four parity combinations of(count[a][p], count[b][p]). These tables store the two smallest values ofcount[a][p] - count[b][p]and the correspondingcount[b][p]value. - As we iterate
j, we update these tables with information from prefixp = j-k. - For the current
j, we determine the required parities forp. We query our tables for the bestp. If the bestp(frommin1) violates the non-zero constraint (i.e.,count[b][p] == count[b][j]), we use the second-bestp(frommin2). - The overall maximum difference is updated in each step.
Walkthrough
For every distinct pair of characters (a, b), we aim to find the maximum value of freq(a) - freq(b). We can express the frequency of a character in a substring s[i..j] using prefix sums: freq(c, i, j) = prefix_sum[c][j] - prefix_sum[c][i-1]. The expression to maximize becomes (count[a][j] - count[b][j]) - (count[a][i-1] - count[b][i-1]).
We can iterate through all possible end points j and for each j, find the best start point i (or p = i-1). The best p is one that minimizes count[a][p] - count[b][p] while satisfying the problem's constraints. The constraints on freq(a) and freq(b) translate to parity conditions on the prefix sums at indices j and p.
To efficiently find the best p for each j, we maintain tables that store the minimum values of count[a][p] - count[b][p] seen so far, categorized by the parity of count[a][p] and count[b][p]. The tricky part is the freq(b) != 0 constraint, which means count[b][p] != count[b][j]. To handle this, we don't just store the minimum value for each parity state, but the two smallest distinct values. If the best minimum corresponds to a p where count[b][p] == count[b][j], we can fall back to the second minimum, ensuring the non-zero constraint is met.
class Solution { // Helper class to store value and corresponding count of character 'b' static class Info { int value; int countB; Info(int value, int countB) { this.value = value; this.countB = countB; } } public int maxDiff(String s, int k) { int n = s.length(); int[][] prefixCounts = new int[5][n + 1]; for (int i = 0; i < n; i++) { for (int c = 0; c < 5; c++) { prefixCounts[c][i + 1] = prefixCounts[c][i]; } prefixCounts[s.charAt(i) - '0'][i + 1]++; } int maxDifference = Integer.MIN_VALUE; for (int a = 0; a < 5; a++) { for (int b = 0; b < 5; b++) { if (a == b) continue; Info[][] min1 = new Info[2][2]; Info[][] min2 = new Info[2][2]; for(int i=0; i<2; i++) for(int j=0; j<2; j++) { min1[i][j] = new Info(Integer.MAX_VALUE, -1); min2[i][j] = new Info(Integer.MAX_VALUE, -1); } // Base case for empty prefix (p = -1) min1[0][0] = new Info(0, 0); for (int j = 0; j < n; j++) { int p = j - k + 1; if (p >= 0) { // Corresponds to prefix ending at p-1 int pa_p = prefixCounts[a][p] % 2; int pb_p = prefixCounts[b][p] % 2; int val_p = prefixCounts[a][p] - prefixCounts[b][p]; int cb_p = prefixCounts[b][p]; // Update min1 and min2 tables if (val_p < min1[pa_p][pb_p].value) { min2[pa_p][pb_p] = min1[pa_p][pb_p]; min1[pa_p][pb_p] = new Info(val_p, cb_p); } else if (val_p > min1[pa_p][pb_p].value && val_p < min2[pa_p][pb_p].value) { min2[pa_p][pb_p] = new Info(val_p, cb_p); } } if (j >= k - 1) { int pa_j = prefixCounts[a][j + 1] % 2; int pb_j = prefixCounts[b][j + 1] % 2; int val_j = prefixCounts[a][j + 1] - prefixCounts[b][j + 1]; int cb_j = prefixCounts[b][j + 1]; int target_pa = (1 - pa_j + 2) % 2; int target_pb = pb_j; Info bestP = min1[target_pa][target_pb]; if (bestP.value != Integer.MAX_VALUE) { if (bestP.countB != cb_j) { maxDifference = Math.max(maxDifference, val_j - bestP.value); } else { Info secondBestP = min2[target_pa][target_pb]; if (secondBestP.value != Integer.MAX_VALUE) { maxDifference = Math.max(maxDifference, val_j - secondBestP.value); } } } } } } } return maxDifference; }}Complexity
Time
O(N * C²), where N is the string length and C is the alphabet size. We iterate through all C*(C-1) pairs of characters, and for each pair, we perform a single O(N) pass. Since C is a small constant (5), the complexity is effectively linear, O(N).
Space
O(N * C), where N is the string length and C is the alphabet size (5). This is for storing the prefix sums. The state tables (`min1`, `min2`) take constant space O(1) for each pair of (a, b).
Trade-offs
Pros
Highly efficient with linear time complexity.
Guaranteed to pass within time limits for the given constraints.
Cons
More complex to implement due to the state management with two minimums and parity conditions.
Solutions
Solution
class Solution {public int maxDifference(String S, int k) { char[] s = S.toCharArray(); int n = s.length; final int inf = Integer.MAX_VALUE / 2; int ans = -inf; for (int a = 0; a < 5; ++a) { for (int b = 0; b < 5; ++b) { if (a == b) { continue; } int curA = 0, curB = 0; int preA = 0, preB = 0; int[][] t = {{inf, inf}, {inf, inf}}; for (int l = -1, r = 0; r < n; ++r) { curA += s[r] == '0' + a ? 1 : 0; curB += s[r] == '0' + b ? 1 : 0; while (r - l >= k && curB - preB >= 2) { t[preA & 1][preB & 1] = Math.min(t[preA & 1][preB & 1], preA - preB); ++l; preA += s[l] == '0' + a ? 1 : 0; preB += s[l] == '0' + b ? 1 : 0; } ans = Math.max(ans, curA - curB - t[curA & 1 ^ 1][curB & 1]); } } } return ans; }}class Solution {public: int maxDifference(string s, int k) { const int n = s.size(); const int inf = INT_MAX / 2; int ans = -inf; for (int a = 0; a < 5; ++a) { for (int b = 0; b < 5; ++b) { if (a == b) { continue; } int curA = 0, curB = 0; int preA = 0, preB = 0; int t[2][2] = {{inf, inf}, {inf, inf}}; int l = -1; for (int r = 0; r < n; ++r) { curA += (s[r] == '0' + a); curB += (s[r] == '0' + b); while (r - l >= k && curB - preB >= 2) { t[preA & 1][preB & 1] = min(t[preA & 1][preB & 1], preA - preB); ++l; preA += (s[l] == '0' + a); preB += (s[l] == '0' + b); } ans = max(ans, curA - curB - t[(curA & 1) ^ 1][curB & 1]); } } } return ans; }};class Solution: def maxDifference(self, S: str, k: int) -> int: s = list(map(int, S)) ans = - inf for a in range(5): for b in range(5): if a == b: continue curA = curB = 0 preA = preB = 0 t = [[inf, inf], [inf, inf]] l = - 1 for r, x in enumerate(s): curA += x == a curB += x == b while r - l >= k and curB - preB >= 2: t[preA & 1][preB & 1] = min(t[preA & 1][preB & 1], preA - preB) l += 1 preA += s[l] == a preB += s[l] == b ans = max(ans, curA - curB - t[curA & 1 ^ 1][curB & 1]) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.