I was solving maximal string (Given a string A generates maximum string doing almost B swaps). I got curious, regarding what if it was exactly K swaps or at least K swaps. I was able to solve atmost K swaps but got stuck in the other 2. The code provided is for atmost K swaps.
void solve1(string a,string &b,int k,int i){
if(i==a.size()|| k==0) return;
for(int j=i+1;j<a.size();j++){
if(a[j]-'0'>a[i]-'0'){
swap(a[j],a[i]);
if(a.compare(b)>0)
b=a;
solve1(a,b,k-1,i+1);
swap(a[j],a[i]);
}
else{
solve1(a,b,k,i+1);
}
}
}
string Solution::solve(string A, int B) {
string b=A;
solve1(A,b,B,0);
return b;
}
How should I change the code to get the desired result, if anyone wondering about test cases, the following line provides the test cases for the other two problems(exactly and at least).
Input:- A = "321" B = 1
Output:- "312"
Hint: Note that you can "waste" two swaps by swapping the same pair of indices twice (i.e. swap $$$A[i]$$$ and $$$A[j]$$$, then swap $$$A[i]$$$ and $$$A[j]$$$ again).
Exactly $$$K$$$ swaps
Let $$$M$$$ be the minimum number of swaps needed to sort $$$A$$$ in descending order, which is the lexicographically largest string we could possibly obtain. If $$$K \leq M$$$, just use the same algorithm as for the "at most $$$K$$$ swaps" problem. If $$$K > M$$$, we will have $$$K - M$$$ leftover swaps after making the string lexicographically largest. Now, if $$$K - M$$$ is even, we can simply waste the remaining swaps two at a time, and keep $$$A$$$ in descending order as our answer. If $$$K - M$$$ is odd, then after wasting two at a time, we are left with one swap. If there exists two equal characters in $$$A$$$, we can swap those two as our final swap and not change $$$A$$$. However, if all characters are distinct, then we have to take the next best option, which is to swap the final two characters and get the 2nd lexicographically largest string.
I originally had a proof for why we cannot get $$$A$$$ sorted descending as our answer in this case based on inversions, but that only applies for adjacent swaps. This fact is still true in general, and a proof of that can be found here.
At least $$$K$$$ swaps
Same as "exactly $$$K$$$ swaps" except we don't have to worry about odd or even $$$K - M$$$, because we can always just do one more swap operation to balance out the parity.