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.

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

stringhighestValuePalindrome(strings,intn,intk){// change to true when the 's' is checked to be a valid palindromeboolisValid=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 kvector<bool>touched(n,false);// 1st round - use k to turn 's' into valid palindromeintl=0,r=s.size()-1;// the right and left index to swhile(k>=0andl<=r){// whenever s[l]] != s[r], one of them need to changed// always change the smaller digit to the larger oneif(s[l]!=s[r]){charlargerCh=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>randk>=0;cout<<"after 1st round - "<<s<<endl;// 2nd round - use remaining k to maximize 's'l=0;r=s.size()-1;intkToUse=0;while(isValidandk>=0andl<=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 biggerkToUse=0;kToUse+=(s[l]!='9')and(nottouched[l]);kToUse+=(r!=l)and(s[r]!='9')and(nottouched[r]);if(k>=kToUse){s[l]='9';s[r]='9';k-=kToUse;}++l;--r;}if(isValid)returns;elsereturn"-1";}

## Highest Value Palindrome

You are viewing a single comment's thread. Return to all 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`

alreadysee comments in the code below for all details