use std::collections::HashMap;

impl Solution {
    pub fn alphabet_board_path(target: String) -> String {
        let mut map: HashMap<char, (i32, i32)> = HashMap::new();
        let alphabet: Vec<char> = "abcdefghijklmnopqrstuvwxyz".chars().collect();
        for i in 0..26 {
            map.insert(alphabet[i], (i as i32 / 5, i as i32 % 5));
        }
        let (mut t, mut ans, mut dx, mut dy) : (String, String, i32, i32) = (
            target.clone(), "".to_string(), 0, 0);
        t.insert(0, 'a');

        for i in 1..t.len() {
            let (cur, prev) = (map.get(&t.chars().nth(i).unwrap()).unwrap(),
            map.get(&t.chars().nth(i - 1).unwrap()).unwrap());
            dx = cur.0 - prev.0; dy = cur.1 - prev.1;
            if dy < 0 {
                ans.push_str(&(0..dy * -1).map(|_| "L").collect::<String>());
            }
            if dx < 0 {
                ans.push_str(&(0..dx * -1).map(|_| "U").collect::<String>());
            }
            if dy > 0 {
                ans.push_str(&(0..dy).map(|_| "R").collect::<String>());
            }
            if dx > 0 {
                ans.push_str(&(0..dx).map(|_| "D").collect::<String>());
            }
            ans.push('!');
        }
        return ans;
    }
}

impl Solution {
    pub fn longest_common_subsequence(text1: String, text2: String) -> i32 {
        let (m, n, mut i, mut j) = (text1.len(), text2.len(), 0, 0);
        let mut dp = vec![vec![0; n + 1]; m + 1];
        while i < m {
            while j < n {
                if text1.chars().nth(i).unwrap() == text2.chars().nth(j).unwrap() {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {
                    dp[i + 1][j + 1] = std::cmp::max(dp[i][j + 1], dp[i + 1][j]);
                }
                j += 1;
            }
            i += 1;
        }
        return dp[m][n];
    }
}

impl Solution {
    pub fn moves_to_make_zigzag(nums: Vec<i32>) -> i32 {
        use std::cmp;
        let mut moves = vec![0, 0];
        let (mut l, mut r) = (0, 0);
        for i in 0..nums.len() {
            if i == 0 {
                l = std::i32::MAX;
            } else {
                l = nums[i - 1];
            }
            if i == nums.len() - 1 {
                r = std::i32::MAX;
            } else {
                r = nums[i + 1];
            }
            
            moves[i % 2] += cmp::max(0, nums[i] - cmp::min(l, r) + 1);
        }
        return std::cmp::min(moves[0], moves[1]);
    }
}