use std::collections::{BinaryHeap, HashMap};

impl Solution {
    pub fn reorganize_string(s: String) -> String {
        let mut map: HashMap<char, i32> = HashMap::new();
        let mut heap: BinaryHeap<(i32, char)> = BinaryHeap::new();
        for c in s.chars() {
            let count = map.entry(c).or_insert(0);
            *count += 1;
        }
        let mut ans = "".to_string();
        for (k, v) in &map {
            if *v > ((s.len() + 1) / 2) as i32 {
                return ans;
            }
            heap.push((*v, *k));
        }
        while heap.len() >= 2 {
            let (mut t1, mut t2) = (heap.pop().unwrap(), heap.pop().unwrap());
            ans.push(t1.1); ans.push(t2.1);
            t1.0 -= 1; t2.0 -= 1;
            if t1.0 != 0 {
                heap.push(t1);
            }
            if t2.0 != 0 {
                heap.push(t2);
            }
        }

        if !heap.is_empty() {
            let t = heap.pop().unwrap();
            ans.push(t.1);
        }
        return ans;
    }
}

impl Solution {
    pub fn valid_tic_tac_toe(board: Vec<String>) -> bool {
        let (mut turns, mut x_win, mut o_win, mut diag, mut antidiag)
            = (0, false, false, 0, 0);
        let (mut rows, mut cols) = (vec![0; 3], vec![0; 3]);

        for i in 0..3 {
            for j in 0..3 {
                let c = board[i].chars().nth(j).unwrap();

                if c == 'X' {
                    turns += 1; rows[i] += 1; cols[j] += 1;
                    if i == j {
                        diag += 1;
                    }
                    if i + j == 2 {
                        antidiag += 1;
                    }
                } else if c == 'O' {
                    turns -= 1; rows[i] -= 1; cols[j] -= 1;
                    if i == j {
                        diag -= 1;
                    }
                    if i + j == 2 {
                        antidiag -= 1;
                    }
                }
            }
        }

        x_win = (rows[0] == 3 || rows[1] == 3 || rows[2] == 3 ||
            cols[0] == 3 || cols[1] == 3 || cols[2] == 3 ||
            diag == 3 || antidiag == 3);
        o_win = (rows[0] == -3 || rows[1] == -3 || rows[2] == -3 ||
            cols[0] == -3 || cols[1] == -3 || cols[2] == -3 ||
            diag == -3 || antidiag == -3);

        if x_win && turns == 0 || o_win && turns == 1 {
            return false;
        }
        
        return (turns == 0 || turns == 1) && (!x_win || !o_win);
    }
}

impl Solution {
    fn dfs(graph: &Vec<Vec<i32>>, cur: i32, p: Vec<i32>, ans: &mut Vec<Vec<i32>>) {
        let mut path = p.clone();
        path.push(cur);
        if cur as usize == graph.len() - 1 {
            ans.push(path);
        } else {
            for neigh in &graph[cur as usize] {
                Self::dfs(graph, *neigh, path.clone(), ans);
            }
        }
    }

    pub fn all_paths_source_target(graph: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let mut ans = vec![];
        let mut g = graph.clone();
        let path = vec![];
        Self::dfs(&mut g, 0, path, &mut ans);
        return ans;
    }
}