string/

lib.rs

//! # String :: Rusty

#![feature(test)]

extern crate test;

/// 38m Count and Say
struct Sol38;

impl Sol38 {
    /// 1 <= n <= 30
    pub fn count_and_say(n: i32) -> String {
        let mut s = "1".to_string();
        for _ in 0..n - 1 {
            let mut enc = vec![];

            let (mut count, mut prv) = (0, '^');
            for chr in s.chars().chain("$".chars()) {
                if chr == prv {
                    count += 1;
                } else {
                    enc.push((count, prv));
                    (count, prv) = (1, chr);
                }
            }

            println!("-> {:?}", enc);

            let mut t = String::new();
            for (count, chr) in enc.iter().skip(1) {
                t += &format!("{}{}", count, chr);
            }

            s = t;
        }

        println!("** {}", s);

        s
    }
}

/// 65h Valid Number
struct Sol65;

impl Sol65 {
    pub fn is_number(s: String) -> bool {
        // State Transition Table :: State/Input -> State
        // ['0-9', '+|-', '.', 'e', ' ']
        let stt = [
            [0, 0, 0, 0, 0], // State: 0 (*Bad* State)
            [3, 2, 4, 0, 1], // State: 1 (Start/End)
            [3, 0, 4, 0, 0], // State: 2
            [3, 0, 5, 6, 9], // State: 3 (End)
            [5, 0, 0, 0, 0], // State: 4
            [5, 0, 0, 6, 9], // State: 5 (End)
            [8, 7, 0, 0, 0], // State: 6
            [8, 0, 0, 0, 0], // State: 7
            [8, 0, 0, 0, 9], // State: 8 (End)
            [0, 0, 0, 0, 9], // State: 9 (End)
        ];

        let mut cstate = 1; // Current State := <- Start State

        for chr in s.chars() {
            cstate = match chr {
                '0'..='9' => stt[cstate][0],
                '+' | '-' => stt[cstate][1],
                '.' => stt[cstate][2],
                'e' | 'E' => stt[cstate][3],
                ' ' => stt[cstate][4],
                _ => return false, // Bad: input
            }
        }

        matches!(cstate, 3 | 5 | 8 | 9)
    }

    fn is_number_enum(s: String) -> bool {
        #[derive(Debug)]
        enum State {
            Start,
            Sign,
            Dot,
            Int,
            IntDot,
            Decimal,
            E,
            ESign,
            Exp,
        }

        use State::*;

        let mut cstate = Start;
        for chr in s.chars() {
            cstate = match (&cstate, chr) {
                (Start, '+' | '-') => Sign,
                (Start | Sign, '.') => Dot,
                (Start | Sign, '0'..='9') => Int,
                (Dot | IntDot, '0'..='9') => Decimal,
                (Int | Decimal | Exp, '0'..='9') => cstate, // No-Transition
                (Int, '.') => IntDot,
                (Int | Decimal | IntDot, 'e' | 'E') => E,
                (E, '+' | '-') => ESign,
                (E | ESign, '0'..='9') => Exp,

                _ => return false,
            }
        }

        matches!(cstate, Int | IntDot | Decimal | Exp)
    }
}

/// 165m Compare Version Numbers
struct Sol165 {}

impl Sol165 {
    pub fn compare_version(version1: String, version2: String) -> i32 {
        let version1: Vec<_> = version1
            .split('.')
            .flat_map(|rv| rv.parse::<i32>())
            .collect();
        let version2: Vec<_> = version2
            .split('.')
            .flat_map(|rv| rv.parse::<i32>())
            .collect();

        println!("-> {version1:?} {version2:?}");

        version1
            .iter()
            .chain(std::iter::repeat(&0))
            .zip(version2.iter().chain(std::iter::repeat(&0)))
            .take(version1.len().max(version2.len()))
            .inspect(|z| println!("-> {z:?}"))
            .filter(|&(rv1, rv2)| rv1 != rv2)
            .nth(0)
            .map_or(0, |(rv1, rv2)| if rv1 > rv2 { 1 } else { -1 })
    }
}

/// 466h Count The Repetition
struct Sol466 {}

impl Sol466 {
    /// 1 <= L1, L2 <= 100
    pub fn get_max_repetitions(s1: String, n1: i32, s2: String, n2: i32) -> i32 {
        let (mut counts, mut marks) = (vec![0; s2.len() + 1], vec![0; s2.len() + 1]);

        let s2: Vec<_> = s2.chars().collect();

        let (mut count, mut mark) = (0, 0);
        for i in 0..n1 as usize {
            for chr in s1.chars() {
                if chr == s2[mark] {
                    mark += 1;
                }
                if mark == s2.len() {
                    mark = 0;
                    count += 1;
                }
            }

            (counts[i], marks[i]) = (count, mark);
            println!("-> {i} {counts:?} {marks:?}");

            for k in 0..i {
                if marks[k] == mark {
                    let prv = counts[k];
                    let pattern = (counts[i] - counts[k]) * ((n1 - 1 - k as i32) / (i - k) as i32);
                    let rest = counts[k + (n1 as usize - 1 - k) % (i - k)] - counts[k];

                    return (prv + pattern + rest) / n2;
                }
            }
        }

        counts[n1 as usize - 1] / n2
    }
}

/// 804 Unique Morse Code Words
struct Sol804 {}

impl Sol804 {
    pub fn unique_morse_representations(words: Vec<String>) -> i32 {
        use std::collections::HashSet;

        const MORSE: [&str; 26] = [
            ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..",
            "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-",
            "-.--", "--..",
        ];

        let mut codes: HashSet<String> = HashSet::new();
        for word in words.iter() {
            let mut code = String::new();
            for chr in word.chars() {
                if let Some(i) = ('a'..='z').position(|x| x == chr) {
                    code.push_str(MORSE[i]);
                }
            }

            codes.insert(code);
        }
        println!("-> {codes:?}");

        codes.len() as _
    }
}

/// 917 Reverse Only Letters
struct Sol917;

impl Sol917 {
    pub fn reverse_only_letters(s: String) -> String {
        let mut ichr = s.chars().rev().filter(|c| c.is_alphabetic());

        s.chars()
            .flat_map(|c| (!c.is_alphabetic()).then_some(c).or_else(|| ichr.next()))
            .collect()
    }
}

/// 966m Vowel Spellchecker
struct Sol966 {}

impl Sol966 {
    pub fn spellchecker(wordlist: Vec<String>, queries: Vec<String>) -> Vec<String> {
        use std::collections::HashMap;

        let words: HashMap<String, Vec<_>> =
            wordlist.iter().fold(HashMap::new(), |mut words, w| {
                words
                    .entry(
                        w.to_string()
                            .to_lowercase()
                            .chars()
                            .map(|chr| match chr {
                                'a' | 'e' | 'i' | 'o' | 'u' => '*',
                                _ => chr,
                            })
                            .collect(),
                    )
                    .and_modify(|lst| lst.push(w))
                    .or_insert(vec![w]);

                words
            });
        println!("-> {words:?}");

        queries
            .iter()
            .map(|w| {
                let key: String = w
                    .to_lowercase()
                    .chars()
                    .map(|chr| if "aeiou".contains(chr) { '*' } else { chr })
                    .collect();

                if let Some(lst) = words.get(&key) {
                    if lst.contains(&w) {
                        w.to_string()
                    } else {
                        for lw in lst.iter() {
                            if lw.to_lowercase() == w.to_lowercase() {
                                return lw.to_string();
                            }
                        }
                        lst.first().unwrap().to_string()
                    }
                } else {
                    "".to_string()
                }
            })
            .collect()
    }
}

/// 1061m Lexicographically Smallest Equivalent String
struct Sol1061 {}

impl Sol1061 {
    pub fn smallest_equivalent_string(s1: String, s2: String, base_str: String) -> String {
        let mut djset: Vec<_> = (0..26).collect();

        let mut union = |v1, v2| {
            let (v1, v2) = (find(v1, &mut djset), find(v2, &mut djset));
            match v1.cmp(&v2) {
                std::cmp::Ordering::Greater => djset[v1] = v2,
                std::cmp::Ordering::Less => djset[v2] = v1,
                _ => {}
            }
        };

        fn find(v: usize, djset: &mut [usize]) -> usize {
            if djset[v] != v {
                djset[v] = find(djset[v], djset);
            }
            djset[v]
        }

        for (chr1, chr2) in s1.as_bytes().iter().zip(s2.as_bytes().iter()) {
            union((chr1 - b'a') as usize, (chr2 - b'a') as usize);
        }

        println!("-> {djset:?}");

        base_str
            .as_bytes()
            .iter()
            .map(|&chr| (find((chr - b'a') as usize, &mut djset) as u8 + b'a') as char)
            .collect()
    }
}

/// 1078 Occurrences After Bigram
struct Sol1078 {}

impl Sol1078 {
    pub fn find_ocurrences(text: String, first: String, second: String) -> Vec<String> {
        println!(
            ":? {:?}",
            text.split(" ")
                .collect::<Vec<_>>()
                .windows(3)
                .filter(|w| w[0] == first && w[1] == second)
                .map(|w| w[2].to_string())
                .collect::<Vec<_>>()
        );

        text.split(" ")
            .collect::<Vec<_>>()
            .windows(3)
            .fold(vec![], |mut v, w| {
                if w[0] == first && w[1] == second {
                    v.push(w[2].to_string());
                }
                v
            })
    }
}

/// 1154 Days of the Year
struct Sol1154;

impl Sol1154 {
    pub fn day_of_year(date: String) -> i32 {
        let mut days = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];

        let mut vs = vec![];
        for w in date.split('-') {
            vs.push(w.parse::<i32>());
        }

        println!(" -> {:?}", vs);

        let mut dy = 0;
        if let (Ok(year), Ok(month), Ok(day)) = (&vs[0], &vs[1], &vs[2]) {
            dy += day;
            if year % 4 == 0 && (year % 100 != 0 || year % 400 == 0) {
                days[1] += 1;
            }

            for m in 0..month - 1 {
                dy += days[m as usize];
            }
        }

        dy
    }
}

/// 1163h Last Substring in Lexicographical Order
struct Sol1163 {}

impl Sol1163 {
    pub fn last_substring(s: String) -> String {
        let s: Vec<_> = s.chars().collect();
        let n = s.len();

        let (mut i, mut j) = (0, 1);
        while j < n {
            let mut k = 0;
            while j + k < n && s[i + k] == s[j + k] {
                k += 1;
            }

            if j + k < n && s[i + k] < s[j + k] {
                (i, j) = (j, (j + 1).max(i + k + 1));
            } else {
                j += k + 1;
            }
        }

        s.iter().skip(i).collect()
    }
}

/// 1513m Number of Substrings With Only 1s
struct Sol1513 {}

impl Sol1513 {
    pub fn num_sub(s: String) -> i32 {
        const M: usize = 1e9 as usize + 7;

        s.chars()
            .collect::<Vec<char>>()
            .chunk_by(|c, c_next| c == c_next)
            .filter(|chk| chk[0] == '1')
            .inspect(|e| println!("-> {e:?}"))
            .map(|chk| (chk.len() * (chk.len() + 1) / 2) % M)
            .fold(0, |total, n| (total + n) % M) as _
    }
}

/// 1876 Substrings of Size Three with Distinct Characters
struct Sol1876 {}

impl Sol1876 {
    pub fn count_good_substrings(s: String) -> i32 {
        s.chars()
            .collect::<Vec<_>>()
            .windows(3)
            .fold(0, |count, w| {
                if w[0] == w[1] || w[1] == w[2] || w[2] == w[0] {
                    count
                } else {
                    count + 1
                }
            }) as _
    }
}

/// 1957 Delete Characters to Make Fancy String
struct Sol1957 {}

impl Sol1957 {
    pub fn make_fancy_string(s: String) -> String {
        if s.len() < 3 {
            return s;
        }

        println!(
            ":? {:?}",
            s.chars()
                .collect::<Vec<_>>()
                .chunk_by(|&a, &b| a == b)
                .flat_map(|chunk| chunk.iter().take(2.min(chunk.len())).collect::<Vec<_>>())
                .collect::<Vec<_>>()
        );

        let mut chars: Vec<_> = s.chars().collect();

        let mut p = 2;
        for x in 2..chars.len() {
            if chars[x] != chars[p - 1] || chars[x] != chars[p - 2] {
                chars[p] = chars[x];
                p += 1;
            }
        }

        chars[..p].iter().collect()
    }
}

/// 2138 Divide a String Into Group of Size K
struct Sol2138 {}

impl Sol2138 {
    pub fn divide_string(s: String, k: i32, fill: char) -> Vec<String> {
        let mut divs = vec![];

        let k = k as usize;
        for start in (0..=s.len() - k).step_by(k) {
            divs.push(s[start..start + k].to_string());
        }

        if !s.len().is_multiple_of(k) {
            let mut last = s[s.len() / k * k..].to_string();
            for _ in 0..k - s.len() % k {
                last.push(fill);
            }
            divs.push(last);
        }

        divs
    }
}

/// 2269 Find the K-Beauty of a Number
struct Sol2269 {}

impl Sol2269 {
    pub fn divisor_substrings(num: i32, k: i32) -> i32 {
        let k = k as usize;

        let mut count = 0;
        let s = num.to_string();
        for start in 0..=s.len() - k {
            let n = s[start..start + k].parse::<i32>().unwrap();
            if n != 0 && num % n == 0 {
                count += 1;
            }
        }

        count as _
    }
}

/// 2273 Find Resultant Array After Removing Anagrams
struct Sol2273 {}

impl Sol2273 {
    pub fn remove_anagrams(words: Vec<String>) -> Vec<String> {
        let mut fs_prv = [0; 26];
        println!("-> {:p} {fs_prv:?}", &fs_prv);

        words.into_iter().fold(vec![], |mut ls, word| {
            let mut fs = [0; 26];
            word.chars()
                .for_each(|chr| fs[chr.to_digit(36).unwrap() as usize - 10] += 1);

            println!("-> {:p} {fs:?}", &fs);

            if fs_prv != fs {
                ls.push(word);
            }
            fs_prv = fs;
            println!("-> {:p}", &fs_prv);

            ls
        })
    }
}

/// 2315 Count Asterisks
struct Sol2315 {}

impl Sol2315 {
    pub fn count_asterisks(s: String) -> i32 {
        println!(
            ":? {}",
            s.split('|').step_by(2).fold(0, |count, pair| {
                count + pair.chars().filter(|&chr| chr == '*').count()
            })
        );

        s.split('|')
            .enumerate()
            .filter(|(i, _)| i & 1 == 0)
            .map(|(_, pair)| pair)
            .fold(0, |count, pair| {
                count + pair.chars().filter(|&chr| chr == '*').count()
            }) as _
    }
}

/// 2785m Sort Vowels in a String
struct Sol2785 {}

impl Sol2785 {
    pub fn sort_vowels(s: String) -> String {
        let mut vws: Vec<_> = s
            .chars()
            .filter(|&chr| "aAeEiIoOuU".contains(chr))
            .collect();
        vws.sort();
        println!("-> {vws:?}");

        let s: Vec<_> = s
            .chars()
            .map(|chr| if "aAeEiIoOuU".contains(chr) { '*' } else { chr })
            .collect();
        println!("-> {s:?}");

        s.iter()
            .scan(0, |i, &chr| {
                if chr == '*' {
                    *i += 1;
                    Some(vws[*i - 1])
                } else {
                    Some(chr)
                }
            })
            .collect()
    }
}

/// 3330 Find the Original Typed String I
struct Sol3330;

impl Sol3330 {
    pub fn possible_string_count(word: String) -> i32 {
        word.as_bytes()
            .windows(2)
            .fold(1, |count, w| if w[0] == w[1] { count + 1 } else { count })
    }
}

/// 3403h Find the Lexicographically Largest String From the Box I
struct Sol3403 {}

impl Sol3403 {
    pub fn answer_string(word: String, num_friends: i32) -> String {
        if num_friends == 1 {
            return word;
        }

        let n = word.len();
        let mut answer = String::new();
        for i in 0..n {
            let s = &word[i..n.min(i + n - (num_friends as usize - 1))];
            if &answer[..] < s {
                answer = s.to_string();
            }
        }

        answer
    }
}

/// 3442 Maximum Difference Between Even and Odd Frequency I
struct Sol3442 {}

impl Sol3442 {
    pub fn max_difference(s: String) -> i32 {
        use std::collections::HashMap;

        let mut freqs = HashMap::new();
        for chr in s.chars() {
            freqs.entry(chr).and_modify(|f| *f += 1).or_insert(1);
        }

        println!("-> {freqs:?}");

        if let (Some(omax), Some(emin)) = (
            freqs.values().filter(|&f| f & 1 == 1).max(),
            freqs.values().filter(|&f| f & 1 == 0).min(),
        ) {
            return omax - emin;
        }

        0
    }
}

#[cfg(test)]
mod tests;