slidingwindow/
lib.rs

1//! # Rust :: Sliding Window
2
3/// 904m Fruit Into Baskests
4struct Sol904 {}
5
6impl Sol904 {
7    pub fn total_fruit(fruits: Vec<i32>) -> i32 {
8        use std::collections::HashMap;
9
10        let mut types = HashMap::new();
11
12        let mut cur_picks = 0;
13        let mut left = 0;
14
15        fruits.iter().fold(0, |picks, &fruit| {
16            cur_picks += 1;
17            types.entry(fruit).and_modify(|f| *f += 1).or_insert(1);
18
19            println!("-> {types:?}");
20
21            while types.len() > 2 {
22                if let Some(f) = types.get_mut(&fruits[left]) {
23                    *f -= 1;
24                    if *f == 0 {
25                        types.remove(&fruits[left]);
26                    }
27
28                    cur_picks -= 1;
29                    left += 1;
30                }
31            }
32
33            picks.max(cur_picks)
34        })
35    }
36}
37
38/// 1358m Number of Substrings Containing All Three Characters
39struct Sol1358;
40
41impl Sol1358 {
42    pub fn number_of_substrings(s: String) -> i32 {
43        use std::collections::HashMap;
44
45        let mut count = 0;
46        let mut frq = HashMap::new();
47
48        let mut left = 0;
49        for (right, chr) in s.chars().enumerate() {
50            frq.entry(chr).and_modify(|f| *f += 1).or_insert(1);
51
52            println!("-> {frq:?}");
53
54            while frq.len() == 3 {
55                count += s.len() - right;
56
57                let lchr = s.as_bytes()[left] as char;
58                frq.entry(lchr).and_modify(|f| *f -= 1);
59                if frq[&lchr] == 0 {
60                    frq.remove(&lchr);
61                }
62
63                left += 1;
64            }
65        }
66
67        count as i32
68    }
69}
70
71/// 1695m Maximum Erasure Value
72struct Sol1695 {}
73
74impl Sol1695 {
75    pub fn maximum_unique_subarray(nums: Vec<i32>) -> i32 {
76        use std::collections::HashSet;
77
78        let mut wset = HashSet::new();
79        let (mut xsum, mut cur_sum) = (0, 0);
80
81        let mut l = 0;
82        for n in &nums {
83            while wset.contains(n) {
84                cur_sum -= nums[l];
85                wset.remove(&nums[l]);
86                l += 1;
87            }
88
89            cur_sum += n;
90            xsum = xsum.max(cur_sum);
91            wset.insert(n);
92        }
93
94        xsum
95    }
96}
97
98/// 2302h Count Subarrays With Score Less Than K
99struct Sol2302;
100
101impl Sol2302 {
102    pub fn count_subarrays(nums: Vec<i32>, k: i64) -> i64 {
103        fn rusty(nums: Vec<i32>, k: i64) -> i64 {
104            let (mut psum, mut l) = (0, 0);
105            nums.iter()
106                .enumerate()
107                .map(|(r, &n)| {
108                    psum += n as i64;
109                    while psum * (r - l + 1) as i64 >= k {
110                        psum -= nums[l] as i64;
111                        l += 1;
112                    }
113                    r - l + 1
114                })
115                .sum::<usize>() as _
116        }
117        println!(":: {}", rusty(nums.to_vec(), k));
118
119        let mut count = 0;
120
121        let mut l = 0;
122        let mut psum = 0;
123        for (r, n) in nums.iter().map(|&n| n as i64).enumerate() {
124            psum += n;
125            while psum * (r - l + 1) as i64 >= k {
126                psum -= nums[l] as i64;
127                l += 1;
128            }
129            count += r - l + 1;
130        }
131
132        count as i64
133    }
134}
135
136/// 2379m Minimum Recolors to Get K Consecutive Black Blocks
137struct Sol2379;
138
139impl Sol2379 {
140    pub fn minimum_recolors(blocks: String, k: i32) -> i32 {
141        println!(
142            "** {} -> {}",
143            blocks,
144            blocks
145                .as_bytes()
146                .windows(k as usize)
147                .fold(usize::MAX, |recolors, w| recolors
148                    .min(w.iter().filter(|&b| b == &b'W').count()))
149        );
150
151        let mut recolors = i32::MAX;
152
153        let mut cur = 0;
154        let mut left = 0;
155
156        let blocks = blocks.as_bytes();
157        for right in 0..blocks.len() {
158            cur += match blocks[right] {
159                b'W' => 1,
160                _ => 0,
161            };
162
163            if right - left + 1 >= k as usize {
164                recolors = recolors.min(cur);
165
166                cur -= match blocks[left] {
167                    b'W' => 1,
168                    _ => 0,
169                };
170
171                left += 1;
172            }
173        }
174
175        match recolors {
176            i32::MAX => 0,
177            _ => recolors,
178        }
179    }
180}
181
182/// 2401m Longest Nice Subarray
183struct Sol2401;
184
185impl Sol2401 {
186    pub fn longest_nice_subarray(nums: Vec<i32>) -> i32 {
187        nums.iter()
188            .enumerate()
189            .fold((0, 0, 0), |(mut l, xlen, mut bits), (r, &n)| {
190                while bits & n != 0 {
191                    bits ^= nums[l];
192                    l += 1;
193                }
194
195                bits |= n;
196
197                (l, xlen.max(r - l + 1), bits)
198            })
199            .1 as i32
200    }
201}
202
203/// 2444h Count Subarrays With Fixed Bounds
204struct Sol2444;
205
206impl Sol2444 {
207    /// 1 <= Min, Max, N_i <= 10^6
208    pub fn count_subarrays(nums: Vec<i32>, min_k: i32, max_k: i32) -> i64 {
209        let mut count = 0;
210
211        let (mut i_x, mut i_m) = (None, None);
212        let mut l = 0;
213        for (r, &n) in nums.iter().enumerate() {
214            if n < min_k || max_k < n {
215                (i_m, i_x) = (None, None);
216                l = r + 1;
217            } else {
218                if n == min_k {
219                    i_m = Some(r);
220                }
221                if n == max_k {
222                    i_x = Some(r);
223                }
224
225                if let (Some(m), Some(x)) = (i_m, i_x) {
226                    count += x.min(m) - l + 1;
227                }
228            }
229        }
230
231        count as i64
232    }
233}
234
235/// 2537m Count the Number of Good Subarrays
236struct Sol2537;
237
238impl Sol2537 {
239    /// 1 <= N_i, k <= 10^9
240    pub fn count_good(nums: Vec<i32>, k: i32) -> i64 {
241        use std::collections::HashMap;
242
243        let mut freq = HashMap::new();
244        let mut count = 0;
245
246        let mut left = 0;
247        let mut window = 0;
248        for (right, &n) in nums.iter().enumerate() {
249            freq.entry(n).and_modify(|f| *f += 1).or_insert(1);
250
251            let f = freq[&n];
252            window += f * (f - 1) / 2 - (f - 1) * (f - 2) / 2; // ~ f - 1
253
254            println!("-> +W {:?}", (right, window));
255
256            while window >= k {
257                count += nums.len() - right;
258
259                freq.entry(nums[left]).and_modify(|f| *f -= 1);
260
261                let f = freq[&nums[left]];
262                window -= (f + 1) * f / 2 - f * (f - 1) / 2; // ~ f
263
264                println!("-> w- {:?}", (right, window));
265
266                left += 1;
267            }
268        }
269
270        println!("-> {freq:?}");
271
272        count as i64
273    }
274}
275
276/// 2799m Count Complete Subarrays in an Array
277struct Sol2799;
278
279impl Sol2799 {
280    pub fn count_complete_subarrays(nums: Vec<i32>) -> i32 {
281        use std::collections::{HashMap, HashSet};
282
283        let uset: HashSet<i32> = HashSet::from_iter(nums.to_vec());
284        println!("-> {uset:?}");
285
286        let mut left = 0;
287        let mut w = 0;
288
289        let mut frq = HashMap::new();
290        nums.iter().enumerate().fold(0, |mut count, (right, &n)| {
291            frq.entry(n).and_modify(|f| *f += 1).or_insert(1);
292            if frq[&n] == 1 {
293                w += 1;
294            }
295
296            while w == uset.len() {
297                count += nums.len() - right;
298
299                frq.entry(nums[left]).and_modify(|f| *f -= 1);
300                if frq[&nums[left]] == 0 {
301                    w -= 1;
302                }
303                left += 1;
304            }
305
306            count
307        }) as i32
308    }
309}
310
311/// 3191m Minimum Operations to Make Binary Array Elements Equal to One I
312struct Sol3191;
313
314impl Sol3191 {
315    pub fn min_operations(nums: Vec<i32>) -> i32 {
316        let mut ops = 0;
317
318        let mut nums = nums;
319        for s in 0..nums.len() - 2 {
320            if nums[s] == 0 {
321                for w in 0..3 {
322                    nums[s + w] ^= 1;
323                }
324
325                ops += 1;
326            }
327        }
328
329        if nums.contains(&0) {
330            return -1;
331        }
332        ops
333    }
334}
335
336/// 3208m Alternating Groups II
337struct Sol3208;
338
339impl Sol3208 {
340    pub fn number_of_alternating_groups(colors: Vec<i32>, k: i32) -> i32 {
341        let (mut wsize, mut groups) = (1, 0);
342
343        let mut prv = colors[0];
344        for i in 1..colors.len() + k as usize - 1 {
345            let cur = colors[i % colors.len()];
346            match cur.cmp(&prv) {
347                std::cmp::Ordering::Equal => wsize = 1,
348                _ => {
349                    wsize += 1;
350                    if wsize >= k {
351                        groups += 1;
352                    }
353                    prv = cur;
354                }
355            }
356        }
357
358        groups
359    }
360}
361
362/// 3306m Count of Substrings Containing Every Vowel and K Consonants II
363struct Sol3306;
364
365impl Sol3306 {
366    pub fn count_of_substrings(word: String, k: i32) -> i64 {
367        println!("** {:?}", (&word, k));
368
369        fn n_least(word: &str, k: i32) -> i64 {
370            use std::collections::HashMap;
371
372            let mut frq = HashMap::new();
373            let mut k = k;
374
375            let mut l = 0;
376            let mut count = 0;
377            for (r, chr) in word.chars().enumerate() {
378                match chr {
379                    'a' | 'e' | 'i' | 'o' | 'u' => {
380                        frq.entry(chr).and_modify(|f| *f += 1).or_insert(1);
381                    }
382                    _ => {
383                        k -= 1;
384                    }
385                }
386
387                println!("-> {frq:?}");
388
389                while k <= 0 && frq.len() == 5 {
390                    count += (word.len() - r) as i64;
391
392                    if let Some(lchr) = word[l..].chars().next() {
393                        match lchr {
394                            'a' | 'e' | 'i' | 'o' | 'u' => {
395                                frq.entry(lchr).and_modify(|f| *f -= 1);
396                                if frq[&lchr] == 0 {
397                                    frq.remove(&lchr);
398                                }
399                            }
400                            _ => k += 1,
401                        }
402                    }
403
404                    l += 1;
405                }
406            }
407
408            count
409        }
410
411        n_least(&word, k) - n_least(&word, k + 1)
412    }
413}
414
415/// 3445h Maximum Difference Between Even and Odd Frequency II
416struct Sol3445 {}
417
418impl Sol3445 {
419    pub fn max_difference(s: String, k: i32) -> i32 {
420        let mut xdiff = i32::MIN;
421        let chrs: Vec<_> = s.chars().collect();
422
423        for a in '0'..='4' {
424            for b in '0'..='4' {
425                if a != b {
426                    println!("-> '{a}' '{b}'");
427
428                    let (mut a_right, mut b_right) = (0, 0);
429                    let (mut a_left, mut b_left) = (0, 0);
430
431                    let mut map = [i32::MAX; 4];
432                    let mut left = -1;
433
434                    for (right, &chr) in chrs.iter().enumerate() {
435                        if chr == a {
436                            a_right += 1;
437                        } else if chr == b {
438                            b_right += 1;
439                        }
440
441                        while right as i32 - left >= k && b_right - b_left >= 2 {
442                            let l_map = ((a_left & 1) << 1 | b_left & 1) as usize;
443                            map[l_map] = map[l_map].min(a_left - b_left);
444
445                            left += 1;
446                            if chrs[left as usize] == a {
447                                a_left += 1;
448                            } else if chrs[left as usize] == b {
449                                b_left += 1;
450                            }
451
452                            println!("-> (L) {left} @ {l_map} ({a_left} {b_left}) {map:?}");
453                        }
454
455                        let r_map = ((a_right & 1) << 1 | b_right & 1) as usize;
456                        if map[r_map ^ 2] != i32::MAX {
457                            xdiff = xdiff.max(a_right - b_right - map[r_map ^ 2]);
458                        }
459
460                        println!("-> (R) {right} @ {r_map} ({a_right} {b_right}) {map:?}");
461                    }
462                }
463            }
464        }
465
466        xdiff
467    }
468}
469
470#[cfg(test)]
471mod tests;
slidingwindow/lib.rs

slidingwindow/
lib.rs
