diff options
-rw-r--r-- | max_diff_even_odd_freq2.c | 120 | ||||
-rw-r--r-- | max_diff_even_odd_freq2.py | 78 |
2 files changed, 198 insertions, 0 deletions
diff --git a/max_diff_even_odd_freq2.c b/max_diff_even_odd_freq2.c new file mode 100644 index 0000000..8d32226 --- /dev/null +++ b/max_diff_even_odd_freq2.c @@ -0,0 +1,120 @@ +// 3445. Maximum Difference Between Even and Odd Frequency II +#include "leetcode.h" + +/* + * 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. + */ + +static int upper_bound(const int *arr, int n, int key) { + int low = 0, high = n; + while (low < high) { + int mid = low + ((high - low) >> 1); + if (arr[mid] <= key) + low = mid + 1; + else + high = mid; + } + return low; +} + +int maxDifference(char *s, int k) { + int n = strlen(s); + if (!n || k > n) + return -1; + int (*freq)[5] = malloc(sizeof(int[5]) * n), present[5] = {0}; + if (!freq) + return -1; + for (int i = 0; i < n; i++) { + int c = s[i] - '0'; + if (!i) + memset(freq[i], 0, sizeof(int) * 5); + else + memcpy(freq[i], freq[i - 1], sizeof(int) * 5); + freq[i][c]++; + present[c] = 1; + } + int ans = INT_MIN; + for (int a = 0; a < 5; a++) { + if (!present[a]) + continue; + for (int b = 0; b < 5; b++) { + if (!present[b] || a == b) + continue; + int *idx_list[4], *val_list[4], size[4]; + for (int i = 0; i < 4; i++) { + idx_list[i] = (int *)malloc(sizeof(int) * n); + val_list[i] = (int *)malloc(sizeof(int) * n); + size[i] = 0; + } + int odd = 0, even = 0; + for (int i = 0; i < n; i++) { + int c = s[i] - '0'; + if (c == a) + odd++; + else if (c == b) + even++; + if ((odd & 1) && (even & 1) == 0 && (i + 1) >= k && even > 0) { + int diff = odd - even; + if (diff > ans) + ans = diff; + } + int key1 = ((odd % 2 == 0) ? 1 : 0) << 1 | ((even % 2 == 0) ? 0 : 1); + if (size[key1] > 0) { + int limit = i - k; + if (limit >= 0) { + int pos = upper_bound(idx_list[key1], size[key1], limit); + if (pos > 0) { + int prev = pos - 1, l = 0, r = prev, curr_min = INT_MAX; + while (l <= r) { + int mid = (l + r) >> 1, j = idx_list[key1][mid]; + if (freq[i][b] != freq[j][b]) { + int v = val_list[key1][mid]; + if (v < curr_min) + curr_min = v; + l = mid + 1; + } else + r = mid - 1; + } + if (curr_min != INT_MAX) { + int cur = odd - even - curr_min; + if (cur > ans) + ans = cur; + } + } + } + } + int key2 = (odd % 2) << 1 | (even % 2), curr_diff = odd - even; + if (!size[key2]) { + idx_list[key2][0] = i; + val_list[key2][0] = curr_diff; + size[key2] = 1; + } else { + int prev_min = val_list[key2][size[key2] - 1]; + int new_min = (prev_min < curr_diff) ? prev_min : curr_diff; + idx_list[key2][size[key2]] = i; + val_list[key2][size[key2]] = new_min; + size[key2]++; + } + } + for (int i = 0; i < 4; i++) { + free(idx_list[i]); + free(val_list[i]); + } + } + } + + free(freq); + return (ans == INT_MIN ? -1 : ans); +} + +int main() { + char *s1 = "12233", *s2 = "1122211", *s3 = "110"; + printf("%d\n", maxDifference(s1, 4)); // expect: -1 + printf("%d\n", maxDifference(s2, 3)); // expect: 1 + printf("%d\n", maxDifference(s3, 3)); // expect: -1 +} diff --git a/max_diff_even_odd_freq2.py b/max_diff_even_odd_freq2.py new file mode 100644 index 0000000..a24d3d0 --- /dev/null +++ b/max_diff_even_odd_freq2.py @@ -0,0 +1,78 @@ +# 3445. 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. +""" + + +class fenwick_tree: + inf = float("inf") + + def __init__(self, n): + self.n = n + self.tree = [self.inf] * (n + 1) + + def update(self, i, val): + pos = i + 1 + while pos <= self.n: + self.tree[pos] = min(self.tree[pos], val) + pos += pos & -pos + + def query(self, i): + res, pos = self.inf, i + 1 + while pos > 0: + res = min(res, self.tree[pos]) + pos -= pos & -pos + return res + + +class Solution(object): + def maxDifference(self, s, k): + """ + :type s: str + :type k: int + :rtype: int + """ + n, ans = len(s), float("-inf") + for a in range(5): + for b in range(5): + if a == b: + continue + d = [0] * (n + 1) + pa, pb = [0] * (n + 1), [0] * (n + 1) + cnt_b = [0] * (n + 1) + for i in range(1, n + 1): + digit = int(s[i - 1]) + d[i] = ( + d[i - 1] + (1 if digit == a else 0) - (1 if digit == b else 0) + ) + pa[i] = (pa[i - 1] + (1 if digit == a else 0)) & 1 + pb[i] = (pb[i - 1] + (1 if digit == b else 0)) & 1 + cnt_b[i] = cnt_b[i - 1] + (1 if digit == b else 0) + trees = [[fenwick_tree(n + 1) for _ in range(2)] for _ in range(2)] + for j in range(n + 1): + if j >= k: + idx = j - k + trees[pa[idx]][pb[idx]].update(cnt_b[idx], d[idx]) + if j > 0: + need_p, need_q = ( + 1 - pa[j], + pb[j], + ) + if cnt_b[j] > 0: + best = trees[need_p][need_q].query(cnt_b[j] - 1) + if best != fenwick_tree.inf: + ans = max(ans, d[j] - best) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxDifference(s="12233", k=4)) + print(obj.maxDifference(s="1122211", k=3)) + print(obj.maxDifference(s="110", k=3)) |