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.
Here is my C++ implementation. I tried to make an implementation easy to read. Hope it helps. Complexity is O(n).
stringhighestValuePalindrome(strings,intn,intk){std::vector<int>unsatisfied_indexes;for(inti=0;i<n/2;++i){if(s[i]!=s[n-i-1]){unsatisfied_indexes.push_back(i);}}if(unsatisfied_indexes.size()>k){return"-1";}// Apply minimum possible changes first// After this for loop is completed, the string // will be palindromefor(inti=0;i<unsatisfied_indexes.size();++i){intfirst_index=unsatisfied_indexes[i];intsecond_index=n-unsatisfied_indexes[i]-1;if(s[first_index]>s[second_index]){s[second_index]=s[first_index];}else{s[first_index]=s[second_index];}}intchanges_left=k-unsatisfied_indexes.size();// Starting from the highest digit, try to maximize the palindromefor(inti=0;i<s.size()&&(changes_left>0);++i){intfirst_index=i;intsecond_index=n-i-1;// if it is 9, don't touch itif(s[first_index]!='9'){autoiter=std::find(unsatisfied_indexes.begin(),unsatisfied_indexes.end(),i);// We have already decreased the change count by 1 if we// have visited this index before, so decrease it by 1if(iter!=unsatisfied_indexes.end()){--changes_left;}else{// We haven't visited this index we need to decrease it by 2if(changes_left<2){break;}changes_left-=2;}// Now we can make the actual changes[first_index]='9';s[second_index]='9';}}// Edge case : Change middle element if it is not 9// and if we still have changes leftif(k%2==1&&(changes_left>=1)&&(s[n/2]!='9')){s[n/2]='9';--changes_left;}returns;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Highest Value Palindrome
You are viewing a single comment's thread. Return to all comments →
Here is my C++ implementation. I tried to make an implementation easy to read. Hope it helps. Complexity is O(n).