Maximal string with a slight change..

Revision en1, by ayushrai6699, 2021-06-24 19:45:49

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"

Tags #backtracking, #recursion

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English ayushrai6699 2021-06-24 19:45:49 1110 Initial revision (published)