Intro

use std::collections::HashMap;

impl Solution {
    /* O(b) time, O(1) space (looks like it's O(b) space but it's bounded to
     * having 26 keys 'a'..='z') */
    fn build_freq_map(b: Vec<u8>) -> HashMap<u8, u32> {
        /* Avoid on-the-fly reallocation, only ascii lowercase chars */
        let mut map = HashMap::with_capacity(26);

        for c in b.into_iter() {
            map.entry(c).and_modify(|e| *e += 1).or_insert(1);
        }

        map
    }

    /* O(r + m) time, O(1) space (looks like it's O(r) but it's bounded to having
     * 26 'a'..'z' elements) */
    /* ~4ms runtime for submission tests */
    fn can_construct_ransom_freq(ransom_note: String, magazine: String) -> bool {
        if ransom_note.len() == 0 {
            return true;
        }

        let mut note_freq_map = Self::build_freq_map(ransom_note.into_bytes());

        for c in magazine.into_bytes() {
            if let Some(val) = note_freq_map.get_mut(&c) {
                *val -= 1;
                if *val == 0 {
                    note_freq_map.remove(&c);
                    if note_freq_map.len() == 0 {
                        return true;
                    }
                }
            }
        }

        false
    }

    /* O(r + m) time, O(1) space (looks like it's O(m) but it's bounded to having
     * 26 'a'..'z' elements) */
    /* ~8ms runtime for submission tests */
    /* All intution was (correctly) against this being faster, since it's best-case
     * requires processing all elements of magazine. I saw in the histogram of solutions
     * that there as a 0ms solution, and while I was sure this wasn't it I was curious
     * to see it's runtime.
     */
    fn can_construct_mag_freq(ransom_note: String, magazine: String) -> bool {
        let mut mag_freq_map = Self::build_freq_map(magazine.into_bytes());

        for c in ransom_note.into_bytes() {
            if let Some(val) = mag_freq_map.get_mut(&c) {
                *val -= 1;
                if *val == 0 {
                    mag_freq_map.remove(&c);
                }
            } else {
                return false;
            }
        }

        true
    }

    /* O(r + m) time, O(1) space */
    /* ~0ms runtime for submission tests */
    /* Implements the `ransom_freq` solution with a primitive array. Since there's no
     * more `map.len()` to call it scans the array when it hits val == 0 for the first
     * time
     *
     * Shouldn't be faster given an ideal compiler, but is closer to the optimal asm
     * expression of the solution.
     */
    fn can_construct_ransom_freq_jank(ransom_note: String, magazine: String) -> bool {
        let mut note_freq_map: [u32; 26] = [0; 26];

        if ransom_note.len() == 0 {
            return true;
        }

        for c in ransom_note.into_bytes() {
            note_freq_map[(c - 'a' as u8) as usize] += 1;
        }

        for c in magazine.into_bytes() {
            let val = &mut note_freq_map[(c - 'a' as u8) as usize];
            if *val > 0 {
                *val -= 1;
                /* O(1) scan since note_freq_map doesn't scale w/ problem size. Only
                 * scan when a value hits 0 */
                if *val == 0 && note_freq_map.iter().all(|count| *count == 0) {
                    return true;
                }
            }
        }

        false
    }

    pub fn can_construct(ransom_note: String, magazine: String) -> bool {
        Self::can_construct_ransom_freq_jank(ransom_note, magazine)
    }
}