impl Solution {
    pub fn find_closest_elements(arr: Vec<i32>, k: i32, x: i32) -> Vec<i32> {
        let mut input = arr.clone();
        input.sort_by(|l, r| {
            if (*l - x).abs() < (*r - x).abs() || (*l - x).abs() == (*r - x).abs() && *l < *r {
                return 0.cmp(&1);
            } else {
                return 1.cmp(&0);
            }
        });
        let mut ans = vec![];
        for i in 0..k as usize {
            ans.push(input[i]);
        }
        ans.sort();
        return ans;
    }
}

impl Solution {
    pub fn new_integer(mut n: i32) -> i32 {
        let (mut ans, mut base) = (0, 1);
        while n > 0 {
            ans += n % 9 * base;
            n /= 9;
            base *= 10;
        }
        return ans;
    }
}

impl Solution {
    fn check(s: &String, start: usize, c: i32) -> bool {
        let mut count = c;
        if count < 0 {
            return false;
        }

        for i in start..s.len() {
            let c = s.chars().nth(i).unwrap();
            if c == '(' {
                count += 1;
            } else if c == ')' {
                if count <= 0 {
                    return false;
                }
                count -= 1;
            } else if c == '*' {
                return Self::check(s, i + 1, count + 1) ||
                    Self::check(s, i + 1, count - 1) ||
                    Self::check(s, i + 1, count);
            }
        }
        return count == 0;
    }

    pub fn check_valid_string(s: String) -> bool {
        return Self::check(&s, 0, 0);
    }
}