Highest Value Palindrome

Sort by

recency

|

531 Discussions

|

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

  • + 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?