### ayushrai6699's blog

By ayushrai6699, history, 5 weeks ago,

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"

• 0

»
5 weeks ago, # |
Rev. 2   0

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).

Solution
•  » » 5 weeks ago, # ^ |   0 Thanks, it looks simple now !