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

|

536 Discussions

|

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

  • enix12enix
     + 0 comments
    fn highestValuePalindrome(s: &str, n: i32, k: i32) -> String {
    let mut chs: Vec<char> = s.chars().collect();
    let mut k = k;
    let mut left: usize = 0;
    let mut right: usize = n as usize - 1;
    let mut cnt = 0;
    
    while left < right {
        if chs[left] != chs[right] {
            cnt += 1;
        }
        left += 1;
        right -= 1;
    }
    
    if k < cnt {
        return "-1".to_string();
    }
    
    left = 0;
    right = n as usize - 1;
    let mut changed: Vec<bool> = vec![false;chs.len()/2];
    while left < right {
        if chs[left] > chs[right] {
            chs[right] = chs[left];
            changed[left] = true;
            k -= 1;
        } else if chs[left] < chs[right] {
            chs[left] = chs[right];
            changed[left] = true;
            k -= 1;
        }
        left += 1;
        right -= 1;
    }
    
    left = 0;
    right = n as usize - 1;
    while left < right {
        if k > 0 && changed[left] && chs[left] != '9' {
            k -= 1;
            chs[left] = '9';
            chs[right] = '9';
        } else if k > 1 && !changed[left] && chs[left] != '9' {
            k -= 2;
            chs[left] = '9';
            chs[right] = '9'
        }
        left += 1;
        right -= 1;
    }
    
    if n % 2 == 1 && k > 0 {
        chs[left] = '9';
    }
    
    chs.into_iter().collect()
}

  • quote_unquote
     + 0 comments
    /*
 * Complete the 'highestValuePalindrome' function below.
 *
 * The function is expected to return a STRING.
 * The function accepts following parameters:
 *  1. STRING s
 *  2. INTEGER n
 *  3. INTEGER k
 */

void _print(const set<size_t>& v) {
    for_each(
        v.begin(),
        v.end(),
        [](int t) { cout << t << " "; }
    );
    cout << endl;
}

set<size_t> _f(const string& s) {
    set<size_t> rx;
    size_t n = s.size();
    size_t k = static_cast<size_t>(floor(n / 2));
    size_t j;
    for (size_t i = 0; i < k; ++i) {
        j = n - 1 - i;
        if (s[i] != s[j]) {
            rx.insert(i);
        }
    }
    return rx;
}

char lx(char c1, char c2) {
    return (c1 > c2) ? c1 : c2;
}

string highestValuePalindrome(string s, int n, int k) {
    
    if (k >= n) {
        return string(n, '9');
    }

    size_t i, j;
    
    auto ix = _f(s);
    // _print(ix);
    if (ix.size() > k) { return "-1"; }
    
    for (auto ii: ix) {
        j = n - 1 - ii;
        auto c = lx(s[ii], s[j]);
        s[ii] = c;
        s[j] = c;
        k--;        
    }

    i = 0;
    j = n - 1 - i;
    while ((i < j) && (k > 0)) {
        if (s[i] != '9') {
            if ((ix.find(i) != ix.end()) && (k >= 1)) {
                s[i] = '9';
                s[j] = '9';
                k--;
            } else if (k >= 2) {
                s[i] = '9';
                s[j] = '9';
                k -= 2;
            }
        }
        i++;
        j--;
    }

    if ((k > 0) && (n % 2 == 1)) {
        j = static_cast<size_t>((n - 1) / 2);
        s[j] = '9';
        k--;
    }
    
    return s;
}