Sort by

recency

|

8 Discussions

|

6 months ago+ 0 comments

def highestValuePalindrome(s, n, k):
    s = list(s)
    s = [int(ele) for ele in s]
    
    modified_idxs = set()
    
    # create any palindrom
    for left_idx in range(0, n // 2):
        right_idx = n - 1 - left_idx
        
        if s[left_idx] != s[right_idx]:
            if k >= 1:
                # change one to greater val
                max_val = max(s[left_idx], s[right_idx])
                s[left_idx] = max_val
                s[right_idx] = max_val
                k -= 1
                modified_idxs.add(left_idx)
            else:
                # not palindrome and can't do any more changes so return -1
                return "-1"
                
    # here we know palindrome can be created, now let's max it
    for left_idx in range(0, n // 2):
        if k < 1:
            break
            
        right_idx = n - 1 - left_idx
        
        if s[left_idx] == 9 and s[right_idx] == 9:
            # can't do any better
            continue

        if left_idx in modified_idxs and k >= 1:
            # already modified, so we need just one change to change two numbers
            s[left_idx] = 9
            s[right_idx] = 9
            k -= 1
        elif k >= 2:
            # not modified yet, we need to changes to change to 9s
            s[left_idx] = 9
            s[right_idx] = 9
            k -= 2
        
    # handle middle
    if n % 2 == 1 and k >= 1:
        middle_idx = n // 2
        s[middle_idx] = 9
            
    return "".join([str(ele) for ele in s])

1 year ago+ 1 comment

public static String highestValuePalindrome(String s, int n, int k) {
        StringBuilder sb = new StringBuilder(s);
        Set<Integer> in = new HashSet<>();
        
        
        if(s.length() == 1) {
            return "9";
        }
        
        int total = n%2 ==0 ? n/2: n/2 + 1;
        
        for (int i = 0; i < total; i++) {
                if(sb.charAt(i) != sb.charAt(n - 1 -i)) {
                    if( k > 0) {
                        if( sb.charAt(i) > sb.charAt(n - 1 -i)) {
                            sb.setCharAt(n - 1 -i, sb.charAt(i));
                        } else {
                            sb.setCharAt(i, sb.charAt(n - 1 -i));
                        }
                        in.add(i);
                    } else {
                        return "-1";
                    }
                    k--;
                }
        }
        
        System.out.println("After Validation: " + k + " val: " + sb.toString());
        int j = 0;
        while(k > 0 && j < total) {
            
            if(sb.charAt(j) == '9') {
                j++;
                continue;
            }
            if(in.contains(j)) {
                sb.setCharAt(n - 1 - j, '9');
                sb.setCharAt(j, '9');
                k--;   
            } else {
                if(k == 1) {
                    j++;
                    continue;
                }
                sb.setCharAt(n - 1 -j, '9');
                sb.setCharAt(j, '9');
                k -= 2;
            }
            j++;
        }
        
        if(k > 0 && n%2 != 0) {
            sb.setCharAt(n/2, '9');
        }
        return sb.toString();
    }

View Thread

2 years ago+ 0 comments

Python

def highestValuePalindrome(s, n, k):      
    s = list(s)
    s2=s.copy()
    for i in range(int(n/2)+1):
        if s[i]!=s[n-i-1]:
            s[i]=s[n-i-1]=max(s[i], s[n-i-1])
            k-=1
        if k<0:
            return '-1'
    
    i=0
    while k>0 and i<int(n/2)+1:
        if s[i]!='9':
            if s[i]==s2[i] and s[n-i-1]==s2[n-i-1] and i!=n-i-1:
                if k>=2:
                    s[i]=s[n-i-1]='9'
                    k-=2
            else:
                s[i]=s[n-i-1]='9'
                k-=1
        i+=1
        
    return ''.join(s)

2 years ago+ 0 comments

JS:

Keys:

Watch this video: https://www.youtube.com/watch?v=zeprQpwdCPA
We are first checking: left and right values and moving towards the middle in a while loop… if something does NOT match, we make the change and record that change in our Processed array (i.e. this will tell us what INDEX has been changed) AND when we make a change we decrement value of K - 1; because K tracks how many changes we can make, so we are working backwards
ones we created palindrome and made and recorded the changes in the Processed array, we need to check if K > 0, because we can now make further changes
so if K > 0 we reset taht values of our pointers i(left) and j(right)
while i <= j AND k> 0 we run the new while loop
if str[i] !== 9 we can make a change here
we first check has ANY of the values either left or right been changed? If YES, we make 1 change, and set both str[i] and str[j] to 9 and K - 1; cause 1 change if NOT, we check if K value is bigger than > 1, if so, we make str[i] and str[j] to 9 and K - 2, because we have now made 2 changes.
at the end of every while loop we i++; j = j - 1;
on second while we have end condition that if i === j && k >=1 - i.e. we can still make 1 more change, then str[i] = 9; break; this is for test case 6, where there is middle value and string is made up for 5 characters; because at this point we are in DEAD MIDDLE, so we need to set this middle value to 9; we can do that by either str[i] = 9; OR str[j]=9 makes no difference, since both i and j are dead middle at this stage
finally, just return: s.join(‘’) and it works

function highestValuePalindrome(s, n, k) {

if (n === 1){
    return k == 1 ? '9' : '-1'
}

let firstEl = s[0];

if(k===0 && [...s].every(el=> el===firstEl)){
    console.log('here')
    return s;
}



let i = 0;
let j = n-1;

s = Array.from(s, el=> Number(el));
console.log(s);

let processed = Array(n).fill(false);
console.log("processed: ", processed);


while(i <= j){

    if(k===0){
        return '-1'
    }

    if(s[i] > s[j]){
        s[j] = s[i];
        processed[j] = true;
        k--;
    }

    if(s[i] < s[j]){
        s[i] = s[j];
        processed[i] = true;
        k--;
    }

    i++;
    j--;
    // end of while loop 1
}

console.log(s);
console.log(processed);
console.log(k);


// now handle any remaining conditions

if(k > 0){

    i = 0;
    j = n-1;



    while(i <=j && k > 0){


        if(s[i] != 9){
            if(processed[i] === true || processed[j] === true){
                s[i]=9;
                s[j]=9;
                k--;
            } else {
                if(k > 1){
                    s[i]=9;
                    s[j]=9;
                    k = k - 2;
                }
            }
        }

        i++;
        j--;

        if(i===j && k >=1){
            s[i]=9;
            break;
        }



        // end of while loop 2
    }



}


console.log(s.join(''));
console.log(processed);
console.log(k);

return s.join('')



// ! function end

}

let s1 = '3943'; let n1 = 4; let k1 = 1; // 3993;

let s2 = '777'; let n2 = 3; let k2 = 0;

highestValuePalindrome(s2,n2,k2);

3 years ago+ 0 comments

symmetry, maxize, mid

def highestValuePalindrome(s, n, k):
    # Write your code here
    s=list(s)
    deduct=[0 for i in range(n)]
    # 1. make sure symmetric...deduction=[]
    curr=k
    mid=n//2
    for i in range(mid):
        if s[i] != s[n-1-i]: # need altering
            curr -= 1
            if curr<0:
                return "-1"
            deduct[i]=1
            if s[i]>s[n-1-i]:
                s[n-1-i]=s[i]
            elif s[i]<s[n-1-i]:
                s[i]=s[n-1-i]
            # print(curr,s)
    # 2. maxize...
    for i in range(mid):
        if s[i] != '9' and curr>=2-deduct[i]: # maxize and afford
            s[i] = '9'
            s[n-1-i]='9'
            curr -= (2-deduct[i])
            # print(curr,s)
            if curr==0:
                break
    # 3. special case mid
    if curr>0 and n % 2==1:
        s[mid]='9'
    return "".join(s)

Sort by

|

8 Discussions

|

symmetry, maxize, mid

Cookie support is required to access HackerRank