struct Solution;

#[derive(Debug, PartialEq, Eq, Clone)]
struct Count {
    v: Vec<i32>,
}

impl Count {
    fn new(s: &str) -> Self {
        let mut v: Vec<i32> = vec![0; 256];
        for c in s.chars() {
            v[c as usize] += 1;
        }
        Count { v }
    }

    fn completes(&self, other: &Count) -> bool {
        for i in 0..26 {
            let c: usize = (b'a' + i) as usize;
            if self.v[c] < other.v[c] {
                return false;
            }
        }
        true
    }
}

impl Solution {
    fn shortest_completing_word(license_plate: String, words: Vec<String>) -> String {
        let mut min: Option<String> = None;
        let letters: String = license_plate
            .chars()
            .filter(|c| c.is_alphabetic())
            .collect();
        let lowercase = letters.to_lowercase();
        let count_of_lowercase = Count::new(&lowercase);
        for word in words {
            let count_of_word = Count::new(&word);
            if count_of_word.completes(&count_of_lowercase) {
                if let Some(ref s) = min {
                    if word.len() < s.len() {
                        min = Some(word);
                    }
                } else {
                    min = Some(word);
                }
            }
        }
        min.unwrap()
    }
}

#[test]
fn name() {
    let license_plate = "1s3 PSt".to_string();
    let words: Vec<String> = ["step", "steps", "stripe", "stepple"]
        .iter()
        .map(|s| s.to_string())
        .collect();
    let res = "steps".to_string();
    assert_eq!(
        Solution::shortest_completing_word(license_plate, words),
        res
    );
    let license_plate = "1s3 456".to_string();
    let words: Vec<String> = ["looks", "pest", "stew", "show"]
        .iter()
        .map(|s| s.to_string())
        .collect();
    let res = "pest".to_string();
    assert_eq!(
        Solution::shortest_completing_word(license_plate, words),
        res
    );
}
