Highest Value Palindrome

  • + 0 comments

    Here is my c# solution:

        public static string highestValuePalindrome(string s, int n, int k)
        {
            int left = 0, right = s.Length - 1;
            int remain = k;
            List<char> newS = new List<char>(s);
            List<bool> changedMark = Enumerable.Repeat(false, n).ToList();
            while (left < right){
                if (remain <= 0 && newS[left] != newS[right]) return "-1"; 
                if (newS[left] != newS[right]){
                    remain--;
                    if (newS[left] > newS[right]) newS[right] = newS[left];
                    if (newS[right] > newS[left]) newS[left] = newS[right];
                       changedMark[left] = true; 
                }
                left++;
                right--;
            }
            left = 0; right = s.Length - 1;
            while (remain > 0 && left < right){    
                if (newS[left] != '9'){             
                    if (changedMark[left])
                    { 
                        newS[left] = newS[right] = '9';
                        changedMark[left] = false; 
                        remain --;
                    }
                    else if (remain >= 2){
                        newS[left] = newS[right] = '9';
                        changedMark[left] = false; 
                        remain -=2;
                    }
                }
                left++;
                right--;      
            }     
            if (remain >= 1 && n % 2 == 1) newS[n/2] = '9';
            string result = new string(newS.ToArray());
            return result;
        }
    }