ayushrai6699's blog

By ayushrai6699, history, 3 years ago, In English

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"

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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