Highest Value Palindrome

6 3
092282

992299

function highestValuePalindrome(s, n, k) {
  function getMincnt(s) {
    var cnt = 0
    for (var i = 0; i < s.length / 2; i++) {
      if (s[i] !== s[s.length - 1 - i]) {
        cnt++
      }
    }
    return cnt
  }

  var m = getMincnt(s) // palindrome 만들기 위한 필요 변경 개수
  if (k < m) {
    return -1
  }

  var rest = k - m // 여윳돈(m번의 변경작업을 제외하고 남는 추가 변경작업 기회)
  var sarr = s.split("")

  for (var i = 0; i < n / 2 && k > 0; i++) {
    if (i === n - 1 - i) {
      // 정가운데까지 도착했으면
      sarr[i] = "9"
      break
    }
    if (sarr[i] === sarr[n - 1 - i]) {
      if (sarr[i] === "9") {
        // 양끝이 모두 9인 경우
        continue
      } else {
        // 양끝이 모두 9가 아닌 경우
        if (rest >= 2) {
          // 양끝 값이 이미 같기 때문에 굳이 변경을 하지 않아도 되지만 여윳돈이 있다면 최대값을 만들기 위해 9로 치환하도록 한다
          sarr[i] = "9"
          sarr[n - 1 - i] = "9"
          k -= 2 // 변경작업 2회 사용
          rest -= 2 // 추가작업 찬스 2회 사용(여윳돈 사용))
        } else {
          continue
        }
      }
    } else {
      if (sarr[i] === "9" || sarr[n - 1 - i] === "9") {
        // 양끝 중 하나가 9라면 무조건 9로 세팅
        sarr[i] = "9"
        sarr[n - 1 - i] = "9"
        k-- // 변경작업 1회 사용
      } else {
        if (rest >= 1) {
          // 여윳돈이 있으면 양끝 두개모두 9로 세팅
          sarr[i] = "9"
          sarr[n - 1 - i] = "9"
          k -= 2 // 변경작업 2회 사용
          rest-- // 추가작업 찬스 1회 사용(어짜피 1회는 사용했어야 하는 경우이므로)
        } else {
          // 여윳돈이 없다면 그냥 짝만 맞추고 다음으로
          var max = Math.max(sarr[i], sarr[n - 1 - i])
          sarr[i] = max
          sarr[n - 1 - i] = max
          k-- // 변경작업 1회 사용
        }
      }
    }
  }

  return sarr.join("")
}