fn highestValuePalindrome(s: &str, n: i32, k: i32) -> String {
    let mut chs: Vec<char> = s.chars().collect();
    let mut k = k;
    let mut left: usize = 0;
    let mut right: usize = n as usize - 1;
    let mut cnt = 0;
    
    while left < right {
        if chs[left] != chs[right] {
            cnt += 1;
        }
        left += 1;
        right -= 1;
    }
    
    if k < cnt {
        return "-1".to_string();
    }
    
    left = 0;
    right = n as usize - 1;
    let mut changed: Vec<bool> = vec![false;chs.len()/2];
    while left < right {
        if chs[left] > chs[right] {
            chs[right] = chs[left];
            changed[left] = true;
            k -= 1;
        } else if chs[left] < chs[right] {
            chs[left] = chs[right];
            changed[left] = true;
            k -= 1;
        }
        left += 1;
        right -= 1;
    }
    
    left = 0;
    right = n as usize - 1;
    while left < right {
        if k > 0 && changed[left] && chs[left] != '9' {
            k -= 1;
            chs[left] = '9';
            chs[right] = '9';
        } else if k > 1 && !changed[left] && chs[left] != '9' {
            k -= 2;
            chs[left] = '9';
            chs[right] = '9'
        }
        left += 1;
        right -= 1;
    }
    
    if n % 2 == 1 && k > 0 {
        chs[left] = '9';
    }
    
    chs.into_iter().collect()
}