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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Strings
  4. Highest Value Palindrome
  5. Discussions

Highest Value Palindrome

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 490 Discussions, By:

recency

Please Login in order to post a comment

  • alfruk
    1 week ago+ 0 comments

    Short version, easy to understand

    string highestValuePalindrome(string s, int n, int k) 
    {
        int i = 0;
        std::set< int > visited;
        
        while ( i < s.size() )
        {
            if ( s[ i ] != s[ n - i - 1 ] )
            {
                if ( k == 0 ) return "-1";
                auto value = std::max( s[ i ], s[ n - i - 1 ] );
                s[ i ] = s[ n - i - 1 ] = value;
                k--;
                visited.insert( i );
            }
            i++;
        }
    
        // in here s is a palindrome
    
        i = 0;
        while ( i < s.size() && k > 0 )
        {
            if ( s[ i ] != '9' )
            {
                if ( visited.find( i ) != visited.end() )
                {
                    s[ i ] = s[ n - i - 1 ] = '9';
                    k--;
                }
                else if ( k >= 2 )
                {
                    s[ i ] = s[ n - i - 1 ] = '9';
                    k -= 2;
                }
            }
            
            i++;
        }
        
        if ( n % 2 == 1 && k > 0 ) s[ n/2 ] = '9';
    
        return s;
    }
    
    0|
    Permalink
  • wilsonthongwk
    3 weeks ago+ 0 comments

    This is a solution with time complexity = O(N) and space complexity = O(N). It passes all test cases.

    the solution finds the answer in two rounds. - 1st round: convert s to a valid Palindrome using fewest number of changes; - 2nd round: convert s to a highest number using the remaining available changes.

    1st round finds each char-pair using two indexes, one going from left->right, and one going from right->left.

    2nd round use two indexes to change the leftmost, and rightmost digit to '9'.

    several special cases need to be considered in order to pass all test cases. - case A: if a char at s[i] has been changed once, it is again changed to 9 in 2nd round, we need to make sure these two "actions" is counted as only one "changes". - case B: 2nd round needs to take care when s[i] itself is 9 already

    see comments in the code below for all details

    string highestValuePalindrome(string s, int n, int k) {
        
        // change to true when the 's' is checked to be a valid palindrome
        bool isValid = false;
        // mark touched[i] to true if s[i] is changed. thus 
        // we can change s[i] again and again and still use up only one k
        vector<bool> touched(n, false);
        
        // 1st round - use k to turn 's' into valid palindrome
        int l=0, r=s.size()-1; // the right and left index to s
        while (k>=0 and l<=r) {
            // whenever s[l]] != s[r], one of them need to changed
            // always change the smaller digit to the larger one
            if (s[l] != s[r]) {
                char largerCh = max(s[l], s[r]);
                touched[l] = largerCh != s[l];
                touched[r] = largerCh != s[r];
                s[l] = largerCh;
                s[r] = largerCh;
                --k;
            }
            ++l;
            --r;
        }
        isValid = l>r and k>=0;
        cout << "after 1st round - " << s << endl;
        
        // 2nd round - use remaining k to maximize 's'
        l=0;
        r=s.size()-1;
        int kToUse = 0;
        while (isValid and k>=0 and l<=r) {
            // change MSB to '9' whenever we still have k to use
            // note change we can also change s[i] without using any k
            // if touched[i] is true. also if s[i] is already '9' we 
            // don't need to change it any bigger
            
            kToUse = 0;
            kToUse += (s[l] != '9') and (not touched[l]);
            kToUse += (r != l) and (s[r] != '9') and (not touched[r]);     
            if (k >= kToUse) {
                s[l] = '9';
                s[r] = '9'; 
                k -= kToUse;
            }
            ++l;
            --r;
        }
        
        if (isValid) return s;
        else return "-1";
    }
    
    0|
    Permalink
  • nonjosh
    2 months ago+ 0 comments

    Python3

    def highestValuePalindrome(s, n, k):
        # Write your code here
        # Check minimum number of changes needed to make it a palindrome
        min_count = 0
        min_change_index_list = []
        for i in range(n // 2):
            if s[i] != s[-1 - i]:
                min_count += 1
                min_change_index_list.append(i)
        if min_count > k:
            return "-1"
    
        # Make it with the minimum number of changes
        s = list(s)
        for i in min_change_index_list:
            s[i] = s[-1 - i] = max(s[i], s[-1 - i])
    
        # Return immediately if min_count == k
        if min_count == k:
            return "".join(s)
    
        # Make it with the maximum number of changes
        # Get index for making highest value
        max_change_index_list = []
        max_count = k - min_count
        for i in range(n // 2):
            if max_count == 0:
                break
            if s[i] != "9" and s[-1 - i] != "9":
                if i in min_change_index_list:
                    max_count -= 1
                    max_change_index_list.append(i)
                elif max_count >= 2:
                    max_change_index_list.append(i)
                    max_count -= 2
        for i in max_change_index_list:
            s[i] = s[-1 - i] = "9"
        if n % 2 == 1 and max_count > 0:
            s[n // 2] = "9"
        return "".join(s)
    
    0|
    Permalink
  • yashdeora98294
    3 months ago+ 0 comments

    Here is Highest value palindrome problem solution in Python Java C++ and C programming - https://programs.programmingoneonone.com/2021/07/hackerrank-highest-value-palindrome-problem-solution.html

    0|
    Permalink
  • hoang_huy_tran01
    3 months ago+ 0 comments

    Hey guys,

    I just found an improvement which can be made to the editorial.

    The solution in editorial doesn't cover the case that maximise the smallest palindrome element first. Apparently it maximises the value from left to right.

    Try this edge case to see what I mean: s = '81118' k = 2

    the highest value palindrome is 89198 with 2 changes. However the solution outputs 91119.

    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy