3445. Maximum Difference Between Even and Odd Frequency II LeetCode Solution
In this guide, you will get 3445. Maximum Difference Between Even and Odd Frequency II LeetCode Solution with the best time and space complexity. The solution to Maximum Difference Between Even and Odd Frequency II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Difference Between Even and Odd Frequency II
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.
Character a has an odd frequency in subs.
Character b has an 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.
3 <= s.length <= 3 * 104
s consists 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
Complexity Analysis
Time Complexity: O(20n) = O(n)
Space Complexity: O(n)
3445. Maximum Difference Between Even and Odd Frequency II LeetCode Solution in C++
class Solution {
public:
int maxDifference(string s, int k) {
int ans = INT_MIN;
for (const auto& [a, b] : getPermutations()) {
// minDiff[parityA][parityB] := min(a - b) of all valid windows with
// parityA and parityB
vector<vector<int>> minDiff(2, vector<int>(2, INT_MAX / 2));
vector<int> prefixA{0}; // prefixA[i] := the number of 'a's in s[0..i)
vector<int> prefixB{0}; // prefixB[i] := the number of 'b's in s[0..i)
for (int l = 0, r = 0; r < s.length(); ++r) {
prefixA.push_back(prefixA.back() + (s[r] == a ? 1 : 0));
prefixB.push_back(prefixB.back() + (s[r] == b ? 1 : 0));
while (r - l + 1 >= k && // the window size >= k
prefixA[l] < prefixA.back() && // the number of 'a's > 0
prefixB[l] < prefixB.back()) { // the number of 'b's > 0
minDiff[prefixA[l] % 2][prefixB[l] % 2] = min(
minDiff[prefixA[l] % 2][prefixB[l] % 2], prefixA[l] - prefixB[l]);
++l;
}
ans = max(ans, (prefixA.back() - prefixB.back()) -
minDiff[1 - prefixA.back() % 2][prefixB.back() % 2]);
}
}
return ans;
}
private:
vector<pair<char, char>> getPermutations() {
vector<pair<char, char>> permutations;
for (const char a : "01234")
for (const char b : "01234")
if (a != b)
permutations.emplace_back(a, b);
return permutations;
}
}; /* code provided by PROGIEZ */
3445. Maximum Difference Between Even and Odd Frequency II LeetCode Solution in Java
class Solution {
public int maxDifference(String s, int k) {
int ans = Integer.MIN_VALUE;
for (Pair<Character, Character> pair : getPermutations()) {
final char a = pair.getKey();
final char b = pair.getValue();
// minDiff[parityA][parityB] := min(a - b) of all valid windows with
// parityA and parityB
int[][] minDiff = new int[2][2];
Arrays.stream(minDiff).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE / 2));
// prefixA[i] := the number of 'a's in s[0..i)
List<Integer> prefixA = new ArrayList<>(List.of(0));
// prefixB[i] := the number of 'b's in s[0..i)
List<Integer> prefixB = new ArrayList<>(List.of(0));
for (int l = 0, r = 0; r < s.length(); ++r) {
prefixA.add(prefixA.get(prefixA.size() - 1) + (s.charAt(r) == a ? 1 : 0));
prefixB.add(prefixB.get(prefixB.size() - 1) + (s.charAt(r) == b ? 1 : 0));
while (r - l + 1 >= k && // the window size >= k
prefixA.get(l) < prefixA.get(prefixA.size() - 1) && // the number of 'a's > 0
prefixB.get(l) < prefixB.get(prefixB.size() - 1)) { // the number of 'b's > 0
minDiff[prefixA.get(l) % 2][prefixB.get(l) % 2] = Math.min(
minDiff[prefixA.get(l) % 2][prefixB.get(l) % 2], prefixA.get(l) - prefixB.get(l));
++l;
}
ans = Math.max(ans, (prefixA.get(prefixA.size() - 1) - prefixB.get(prefixB.size() - 1)) -
minDiff[1 - prefixA.get(prefixA.size() - 1) % 2]
[prefixB.get(prefixB.size() - 1) % 2]);
}
}
return ans;
}
private List<Pair<Character, Character>> getPermutations() {
List<Pair<Character, Character>> permutations = new ArrayList<>();
for (final char a : "01234".toCharArray())
for (final char b : "01234".toCharArray())
if (a != b)
permutations.add(new Pair<>(a, b));
return permutations;
}
} // code provided by PROGIEZ
3445. Maximum Difference Between Even and Odd Frequency II LeetCode Solution in Python
class Solution:
def maxDifference(self, s: str, k: int) -> int:
ans = -math.inf
permutations = [(a, b) for a in '01234' for b in '01234' if a != b]
for a, b in permutations:
# minDiff[(parityA, parityB)] := min(a - b) of all valid windows with
# parityA and parityB
minDiff = collections.defaultdict(lambda: math.inf)
prefixA = [0] # prefixA[i] := the number of 'a's in s[0..i)
prefixB = [0] # prefixB[i] := the number of 'b's in s[0..i)
l = 0
for r, c in enumerate(s):
prefixA.append(prefixA[-1] + int(c == a))
prefixB.append(prefixB[-1] + int(c == b))
while (r - l + 1 >= k and # the window size >= k
prefixA[l] < prefixA[-1] and # the number of 'a's > 0
prefixB[l] < prefixB[-1]): # the number of 'b's > 0
paritiesKey = (prefixA[l] % 2, prefixB[l] % 2)
minDiff[paritiesKey] = min(minDiff[paritiesKey],
prefixA[l] - prefixB[l])
l += 1
ans = max(ans, (prefixA[-1] - prefixB[-1]) -
minDiff[(1 - prefixA[-1] % 2, prefixB[-1] % 2)])
return ans # code by PROGIEZ
