LeetCode #340 & #76

lib.rs

use std::hash::Hash;
use std::collections::{HashMap, VecDeque};
use std::cmp::max;

// This is meant to be an introductory problem to the technique. The question is, given
// a list of numbers and a number k, return the largest sum of k
// consecutive numbers in the list.
pub fn largest_continuous_sum(nums: Vec<isize>, k: usize) -> isize {
    if nums.len() < k {
        // undefined behavior
        return 0;
    }
    let mut current: isize = nums.iter().take(k).sum();
    let mut best = current;
    // sliding window
    for (head, tail) in nums[k..].iter().zip(nums.iter()) {
        current = current + head - tail;
        best = max(best, current);
    }
    best
}


// Counter is available in a crate, but just for fun I create one myself
#[derive(Debug)]
pub struct Counter<T: Hash + PartialEq + Eq + Clone + Copy> {
    counts: HashMap<T, isize>, // having signed values is useful for the second leetcode problem
    n_unique: usize
}

#[derive(Debug)]
pub struct WindowCounter<T: Hash + PartialEq + Eq + Clone + Copy> {
    counter: Counter<T>,
    // store the window inside the structure. Worst case this copies the whole string.
    // you could alternatively store the window as reference + index + len
    window: VecDeque<T>,
    // if invert is true, count down when adding and count up when removing
    // this makes it convenient to use for task 2
    invert: bool
}

impl<T: Hash + PartialEq + Eq + Clone + Copy> Counter<T> {
    pub fn new() -> Counter<T> {
        Counter{counts: HashMap::new(), n_unique: 0}
    }

    pub fn unique(&self) -> usize {
        self.n_unique
    }

    pub fn contains(&self, val: T) -> bool {
        match self.counts.get(&val) {
            Some(val) => *val > 0,
            None => false
        }
    }

    pub fn get_count(&self, val: T) -> isize {
        *self.counts.get(&val).unwrap_or(&0)
    }

    pub fn add(&mut self, val: T) {
        if let Some(count) = self.counts.get_mut(&val) {
            *count += 1;
            if *count == 1 {
                self.n_unique += 1;
            }
        } else {
            self.counts.insert(val, 1);
            self.n_unique += 1;
        }
    }

    pub fn remove(&mut self, val: T) {
        if let Some(count) = self.counts.get_mut(&val) {
            *count -= 1;
            if *count == 0 {
                self.counts.remove(&val);
                self.n_unique -= 1;
            }
        } else {
            self.counts.insert(val, -1);
        }
    }

    pub fn is_empty(&self) -> bool {
        self.n_unique == 0
    }
}

impl<T: Hash + PartialEq + Eq + Clone + Copy> WindowCounter<T> {
    pub fn new(invert: bool) -> WindowCounter<T> {
        WindowCounter{counter: Counter::new(), window: VecDeque::new(), invert}
    }

    pub fn from_counter(counter: Counter<T>, invert: bool) -> WindowCounter<T> {
        // pre-initialized counter
        WindowCounter{counter, window: VecDeque::new(), invert}
    }

    pub fn unique(&self) -> usize {
        self.counter.unique()
    }

    pub fn contains(&self, val: T) -> bool {
        self.counter.contains(val)
    }

    pub fn get_count(&self, val: T) -> isize {
        self.counter.get_count(val)
    }

    pub fn add(&mut self, val: T) {
        if !self.invert {
            self.counter.add(val);
        } else {
            self.counter.remove(val);
        }
        self.window.push_back(val);
    }

    pub fn pop(&mut self) -> Option<T> {
        // remove the oldest inserted value
        let old = self.window.pop_front();
        if let Some(val) = old {
            if !self.invert {
                self.counter.remove(val);
            } else {
                self.counter.add(val);
            }
        }
        old
    }

    pub fn is_empty(&self) -> bool {
        self.counter.is_empty()
    }
}

// https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/description/
pub fn longest_substring_with_k_distinct_chars(s: &str, k: usize) -> usize {
    let mut counter: WindowCounter<char> = WindowCounter::new(false);
    let mut best = 0;
    let mut current = 0;
    if k == 0 {
        // undefined behavior
        return 0;
    }
    for c in s.chars() {
        // add the next char
        counter.add(c);
        current += 1;
        // move tail to the right if necessary
        while counter.unique() > k {
            counter.pop();
            current -= 1;
        }
        assert!(counter.unique() <= k);
        best = max(best, current);
    }
    best
}

// https://leetcode.com/problems/minimum-window-substring/description/
pub fn min_window_substring(s: &str, t: &str) -> String {
    if t.len() == 0 {
        return String::new();
    }

    // count the chars in t
    let mut startcounter = Counter::new();
    for c in t.chars() {
        startcounter.add(c);
    }

    // tcounter tracks how many of t's chars are missing
    // in the current window
    let mut tcounter = WindowCounter::from_counter(startcounter, true);
    let mut start = 0usize;
    let mut end = 0usize;
    let mut best: Option<&str> = None;

    for c in s.chars() {
        //invariants
        assert!(end >= start);
        assert!(tcounter.unique() > 0);

        // we haven't got all chars of t yet, extend window to the right
        tcounter.add(c);
        end += c.len_utf8();
        if tcounter.unique() <= 0 {
            // found a candidate, prune from the left to find minimum possible length
            let mut popped = tcounter.pop().unwrap();
            while tcounter.unique() <= 0 {
                start += popped.len_utf8();
                popped = tcounter.pop().unwrap();
            }

            // update current best if necessary
            if best.is_none() || best.is_some_and(|s| s.len() > end - start) {
                best = Some(&s[start..end]);
            }

            // we are done looking at s[0..=start]
            start += popped.len_utf8();
        }
    }

    match best {
        Some(result) => String::from(result),
        None => String::new()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_largest_continuous_sum() {
        let nums = vec![1, 2, 3, 4, 5];
        let k = 3;
        assert_eq!(largest_continuous_sum(nums, k), 12);

        let nums = vec![1, 2, 3, -4, 5];
        let k = 3;
        assert_eq!(largest_continuous_sum(nums, k), 6);
    }

    #[test]
    fn test_longest_substring_with_k_distinct_chars() {
        let s = "araaci";
        let k = 2;
        assert_eq!(longest_substring_with_k_distinct_chars(s, k), 4);

        let s = "araaci";
        let k = 1;
        assert_eq!(longest_substring_with_k_distinct_chars(s, k), 2);

        let s = "cbbebi";
        let k = 3;
        assert_eq!(longest_substring_with_k_distinct_chars(s, k), 5);
    }

    #[test]
    fn test_min_window_substring() {
        let s = "ADOBECODEBANC";
        let t = "ABC";
        assert_eq!(min_window_substring(s, t), "BANC");

        let s = "a";
        let t = "a";
        assert_eq!(min_window_substring(s, t), "a");

        let s = "a";
        let t = "aa";
        assert_eq!(min_window_substring(s, t), "");

        let s = "a";
        let t = "b";
        assert_eq!(min_window_substring(s, t), "");

        let s = "aa";
        let t = "aa";
        assert_eq!(min_window_substring(s, t), "aa");

        let s = "bbaa";
        let t = "aba";
        assert_eq!(min_window_substring(s, t), "baa");

        let s = "bbaa";
        let t = "abb";
        assert_eq!(min_window_substring(s, t), "bba");

        let s = "bbaa";
        let t = "abaaa";
        assert_eq!(min_window_substring(s, t), "");
    }
}