You are given a number (in the form of a string) and an integer k. You have to output the maximum palindromic number that can be formed from the given number and by using at most k changes to the number (replacing digits is the only allowed operations). Output -1 if it is not possible to get a palindrome.
any one have solution?
Can you provide a link? I don’t think dp is needed in this problem. But I would like to check if my logic is correct.
geeksforgeeks link
Ok i see i cant test. Anyways my logic is:
First check out how many positions and which we need to change to make it palindrome. Lets say x positions are needed (consider only one half, we are going to make it equal to the other half.) . Now we have k-x extra changes left. First change those positions where change is needed i.e say at i, s[i]!=s[n-i]. So do s[i]=max(s[i],s[n-i]). Run a greedy algorithm from first position (do everything in first half) . If current position doesnt need a change we see if we can make it larger i.e digit here is not 9. If yes, we will need 2 extra changes if we want to change here. Now suppose pos was a position of change. So we need 1 extra change for this position to make it larger.
1 Like
i understood your logic…thank you…
but one question is how to calculate value of x efficiently?
Its very simple.Just run a loop. while(i<n-i){ if(s[i]!=s[n-i]) x++;}
what is solution , if they ask for swap not for change ??
can you explain in detail. Minimum swaps to form the string palindrome or minimum swaps to make it largest palindrome?
swap to get max palindromic number
ex.
s=111221 k=2
ans = 211112
but if k=1
ans = 112211
I guess same greedyish solution works here too. First lets focus to make it palindromic.Start from max element. Let it’s occurence be at i in first half and j in second. See where you want to fix it i.e whether i and n-i or n-j and j. Note that however you fix it number of swaps remains same(think of it as inversion count problem.) Now we have some more swaps left again start from max element and swap it rightwards. A few more bookkeepings will be needed i guess but something similar will work
I didn’t understand your logic…Can you explain your logic through one example? Thanks in advance…
Yes this is what I thought but why is it tagged under DP?
Beats me. Dp would make more sense if adding/deleting characters was allowed.