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

|

538 Discussions

|

  • naufalfh19
     + 0 comments

    Python3 Solution

    def highestValuePalindrome(s, n, k):
    # Write your code here
    listS = list(s)
    
    l, r = 0, len(s)-1
    count = 0
    while l < r:
        if listS[l] != listS[r]:
            count += 1
            
        l += 1
        r -= 1
    
    if count > k:
        return "-1"

    l, r = 0, len(s)-1
    while l <= r and k > 0:
        if l == r:
            listS[l] = '9'
            k -= 1
            break
            
        if listS[l] != listS[r]:
            if k-2 >= count-1 and listS[l] != '9' and listS[r] != '9':
                listS[l], listS[r] = '9','9'
                k -= 2
                count -= 1
            else:
                listS[l] = max(listS[l], listS[r])
                listS[r] = max(listS[l], listS[r])
                k -= 1
                count -= 1
        else:
            if k-2 >= count and listS[l] != '9':
                listS[l], listS[r] = '9','9'
                k -= 2
                
        
        
        l += 1
        r -= 1
            
    return "".join(listS)

  • jpdunn1970
     + 0 comments

    JAVA 15

    public static String highestValuePalindrome(String s, int n, int k) {
        Set<Integer> mySet = new HashSet<>();
        char[] chArray = s.toCharArray();
        int left = 0, right = chArray.length - 1;
        int count = 0;
        while (left <= right) {
            char leftVal = chArray[left];
            char rightVal = chArray[right];
            if (leftVal != rightVal) {
                mySet.add(left);
                if (leftVal > rightVal) chArray[right] = leftVal;
                else chArray[left] = rightVal;
                count++;
            }
            left ++; right--;
        }
        
        left = 0; right = s.length() -1;
        while (left <= right && count < k) {
            if (chArray[left] != '9') {
                if (mySet.contains(left) || k - count > 1 || left == right) {
                    chArray[left] = '9';
                    chArray[right] = '9';
                }
                if (mySet.contains(left) || left == right) count++;
                else if (k - count > 1) count += 2;
            }
            left ++; right --;
        }
        return count <= k ? new String(chArray) : "-1";
    }

  • mrweisu
     + 0 comments

    My code does not use the typical two phase approach. It finish the changes in one sweep.

    def highestValuePalindrome(s, n, k): # Write your code here

    N = len(s)
s = list(s)

imbalance = 0

for i in range(N//2):
    if s[i] != s[N-1-i]:
        imbalance += 1

if k < imbalance:
    return '-1'

if N % 2 == 1:
    limit = N//2 + 1
else:
    limit = N//2

for i in range(limit):

    if s[i] == '9' and s[N-i-1] == '9': # Best scenario, nothing to do.
        continue

    if s[i] == s[N-1-i] and k >= imbalance + 2: #If there is budget, change both at the cost of losing two counts in the budget and no reduction in imbalance.
        s[i] = '9'
        s[N-i-1] = '9'
        k -= 2
    elif s[i] != s[N-1-i] and (s[i]=='9' or s[N-1-i]=='9'): #if not balanced, but one of them is 9, cost one count in budget and reduce imbalance by 1.
        s[i] = '9'
        s[N-i-1] = '9'
        k -= 1
        imbalance -= 1
    elif s[i] != s[N-1-i] and k >= imbalance + 1: # if both are not 9 and not balanced, change both to 9 only when there is budget.
        s[i] = '9'
        s[N-i-1] = '9'
        k -= 2
        imbalance -= 1
    elif s[i] != s[N-1-i]: # typical change
        if s[i] > s[N-i-1]:
            s[N-i-1] = s[i]
        else:
            s[i] = s[N-i-1]
        k -= 1
        imbalance -= 1
    elif k > 0 and imbalance == 0 and N % 2 ==1:
        s[N//2] = '9'

return ''.join(s)

  • chinthamgopi
     + 0 comments

    def highestValuePalindrome(s, n, k): # convert to list so we can modify characters s = list(s) changed = [False] * n # track positions changed in phase 1 i, j = 0, n - 1 used = 0

    # Phase 1: make the string a palindrome with minimal changes
while i < j:
    if s[i] != s[j]:
        # replace the smaller digit with the larger one
        if s[i] > s[j]:
            s[j] = s[i]
        else:
            s[i] = s[j]
        changed[i] = changed[j] = True
        used += 1
    i += 1
    j -= 1

# if we already used more changes than allowed, impossible
if used > k:
    return '-1'

# Phase 2: maximize the palindrome using remaining changes
remaining = k - used
i, j = 0, n - 1
while i <= j:
    if i == j:
        # middle digit in odd-length string: can make it '9' with one remaining change
        if remaining > 0:
            s[i] = '9'
        # else leave as is
    else:
        if s[i] != '9':
            # if either side was changed in phase 1, upgrading both to '9' costs 1 extra change
            if changed[i] or changed[j]:
                if remaining >= 1:
                    s[i] = s[j] = '9'
                    remaining -= 1
            # if neither side was changed before, upgrading both to '9' costs 2 changes
            elif remaining >= 2:
                s[i] = s[j] = '9'
                remaining -= 2
    i += 1
    j -= 1

return ''.join(s)

  • safee7
     + 0 comments
    void largest_pal(string& s, int n, int& k, vector<bool>& changed){
    int l=0,h=n-1;
    
    while(l<=h && k>0){
        if(l == h){ //middle
            if(k > 0 && s[l] != '9'){
                s[l] = '9';
                k--;
            }
        }
        else {
        if (s[l] != '9') {
            if (changed[l] || changed[h]) {
                // Only 1 change needed to upgrade both to '9'
                if (k >= 1) {
                    s[l] = s[h] = '9';
                    k--;
                }
            } else if (k >= 2) {
                // 2 changes needed to upgrade both to '9'
                s[l] = s[h] = '9';
                k -= 2;
            }
         }
       }
       l++; h--;
    }
}
string highestValuePalindrome(string s, int n, int k) {
    vector<bool>changed(n,false);
    // int val = check_palindrome(s,n,k,changed);
    int l=0,h=n-1;
    //First pass: Make the string a palindrome with minimal changes, record changed positions
    while(l <= h){
        if(s[l] != s[h]){
            
            if(k == 0)
                return "-1";
            
            if(s[l] > s[h])
                s[h] = s[l];
            else 
                s[l] = s[h];
            
            k--;
            changed[l] = changed[h] = true;       
        }
    l++; h--;
    }
    
    //Second pass: Maximize the palindrome by upgrading pairs to '9'
   
    // if(n%2 == 1 && k==1){
    //     s[n/2] = '9';
    //     return s;
    // }
    
        largest_pal(s,n,k,changed);
    
    
    
    return s;
}