slidingwindow/
lib.rs

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

slidingwindow/
lib.rs
