Untitled

mail@pastecode.io avatar
unknown
rust
a month ago
2.1 kB
4
Indexable
Never
impl Solution {
    pub fn min_window(s: String, t: String) -> String {
        let mut char_map: HashMap<char, i32> = HashMap::with_capacity(t.len());

        for c in t.chars() {
            *char_map.entry(c).or_insert(0) += 1;
        }

        let (mut best, mut best_size) = ("", usize::MAX);
        let (need, mut found) = (t.len(), 0);

        let mut window_map: HashMap<char, i32> = HashMap::with_capacity(need);
        let mut window_found: VecDeque<usize> = VecDeque::new();

        for (right, c) in s.chars().enumerate() {
            if let Some(&_) = char_map.get(&c) {
                *window_map.entry(c).or_insert(0) += 1;
                window_found.push_back(right);
                found += 1;

                if found > need {
                    loop {
                        let old_pos = *window_found.front().unwrap();
                        let old = s.chars().nth(old_pos).unwrap();

                        if window_map[&old] > char_map[&old] {
                            window_found.pop_front().unwrap(); // remove old
                            *window_map.get_mut(&old).unwrap() -= 1;
                            found -= 1;
                        } else {
                            break;
                        }
                    }
                }

                #[inline]
                fn contains(map1: &HashMap<char, i32>, map2: &HashMap<char, i32>) -> bool {
                    for (key, &val) in map2 {
                        if val > *map1.get(key).or(Some(&0)).unwrap() {
                            return false;
                        }
                    }
                    true
                }

                if found >= need && contains(&window_map, &char_map) {
                    let left = *window_found.front().unwrap();
                    let size = right - left + 1;

                    if size <= best_size {
                        best = &s[left..right + 1];
                        best_size = size;
                    }
                }
            }
        }

        best.to_string()
    }
}

Leave a Comment