Highest Value Palindrome

Sort by

recency

|

8 Discussions

|

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

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