We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Strings
  4. Highest Value Palindrome
  5. Discussions

Highest Value Palindrome

Sort by

recency

|

531 Discussions

|

  • vituan121002
     + 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;
    }
}

  • Dmitry_Strakhov
     + 0 comments

    Here is my C# solution:

    public static string HighestValuePalindrome(string s, int k) {
        char[] chars = s.ToCharArray();
        
        // calculate count of unbalanced pairs in the string
        int m = 0;
        int i1 = 0;
        int j1 = s.Length - 1;

        while(i1 < j1) {
            if(s[i1] != s[j1])
                m++;
            i1++;
            j1--;
        }

        // it is not enough 'k' in advance
        if(k < m)
            return "-1";

        int i2 = 0;
        int j2 = s.Length - 1;

        // we prefer both '9' if possible
        while(i2 < j2) {
            if(CanSetBoth9Digits()) {
                chars[i2] = chars[j2] = '9';
                k -= 2;
                if(s[i2] != s[j2])
                    m -= 1;
            }
            else if(s[i2] > s[j2]) {
                chars[j2] = chars[i2];
                k--;
                m--;
            }
            else if(s[i2] < s[j2]) {
                chars[i2] = chars[j2];
                k--;
                m--;
            }

            i2++;
            j2--;
        }
        
        if(i2 == j2 && k > 0)
            chars[i2] = '9';
        
        return new string(chars);


        bool CanSetBoth9Digits() {
            if(s[i2] == '9' || s[j2] == '9')
                return false;
            bool digitsEqual = s[i2] == s[j2];
            return (!digitsEqual && k > m) || (digitsEqual && k > m + 1);
        }
    }

  • icywind
     + 0 comments

    **C# Solution O(n) time 0(1) space **

    public static string highestValuePalindrome(string s, int n, int k)
{
    /* Thought process
    if s is palindrome, then easily update
    if s is not palindrome, then need to know how many different pair D.
    If k < D, then nope. Otherwise,
    If k == D, change all half of the diff pairs
    if k > D, after above, change from the furthest out pair to inside
    */
    char[] arr = s.ToArray<char>();
    HashSet<int> updated = new HashSet<int>();
    int l = 0, r = n-1;
    int mid = n/2;
    int replace = k;
    while ( l < r) {
        if (s[l] == s[r]) { 
            l++; r--;
            continue;
        } 
        if (replace>0) {
            if (s[l] > s[r]) {
                arr[r] = arr[l];
            } else {
                arr[l] = arr[r];
            }
            updated.Add(l);
            replace--;
        } else {
            if (l < mid) {
                return "-1";
            }
        }
        l++; r--;
    } 
    l = 0;
    r = n-1;
    while(replace > 0 && l<=r) {
        if (arr[l]<'9') {
            if (l == r) {
                arr[l] = '9';
                break;
            }
            if (updated.Contains(l)) {
                // need one change only, since one is counted to update to non-9
                arr[l] = '9';
                arr[r] = '9';
                replace--;
            } else if (replace > 1) {
                arr[l] = '9';
                arr[r] = '9';
                replace-=2;
            }
        }
        l++; r--;
    }

    return new string(arr);

  • naive_sage
     + 0 comments

    Hi @nabila_ahmed

    You are the author of Highest Value Palindrome problem. I was going through your solution and in your condition below condition else if((mark[l]==1 || mark[r]==1) && k>=1) { k-=1; ans[l] = ans[r] = '9'; } You are decrementing k by 1 but it should be decremented by 2 because we are changing both ans[l] and ans[r] in theelse part which requires 2 moves. If only 1 move is left how is this condition justified!!!

  • naive_sage
     + 0 comments

    @Xromeo

    I saw your solution in JAVA but I have a thing to ask..in the below condition else if (k - changes >= 1 && s.charAt(left) != s.charAt(right)) {

                        chars[left] = '9';
                    chars[right] = '9';
                    changes++;
                }

    In this condition, you are changing two characters but incrementing changes by 1. Why? For the string "092282" with k = 3, I debugged the code and in first loop the array was [2, 9, 2, 2, 9, 2] but in the above condition you are actually changing the values of both left and right index but incrementing the change by 1. I think it should be 2 . Am I mising something in the logic?