diff options
author | Jack Sangdahl <[email protected]> | 2025-06-10 23:40:19 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-06-10 23:40:19 -0600 |
commit | 1276be41988ca8331a45ce13b2d54c32f67a23ce (patch) | |
tree | 51a257ee95b5b2ba84edc3c7ffc87af300a04792 /max_diff_even_odd_freq2.py | |
parent | 766452a24801294dd5558c1f8e566b232e09d8e3 (diff) | |
download | leetcode-1276be41988ca8331a45ce13b2d54c32f67a23ce.tar.gz leetcode-1276be41988ca8331a45ce13b2d54c32f67a23ce.zip |
3445. maximum difference between even and odd frequency 2
Diffstat (limited to 'max_diff_even_odd_freq2.py')
-rw-r--r-- | max_diff_even_odd_freq2.py | 78 |
1 files changed, 78 insertions, 0 deletions
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)) |