Highest Value Palindrome
Highest Value Palindrome
+ 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 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: converts
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 is9
alreadysee 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 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 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 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.
Sort 490 Discussions, By:
Please Login in order to post a comment