CareerCup

Here's a simple code in C++.

Iterate over the permuted string and find the first position in original string which is equal to the current character of permuted. Then go back and swap one by one.

O(n^2)

void Swapping(string S,string T)
{

	for (int i=0;i<S.size();i++){
		int j=i;

		while (S[j]!=T[i])j++;
		while (j>i){
			swap(S[j],S[j-1]);
			cout << S << endl;
			j--;
		}
	}

}

int search(string src, int s, char ch)
{
    for(int i=s;i<src.length();i++)
    {
        if(src[i] == ch)
            return i;
    }
    return -1;
}           
    
void pathSrc2Dst(string src, string dst)
{
    int lenS = src.length();
    int lenD = dst.length();
    
    if(lenS != lenD)
    {
        cout<<"  Invalid Input "<<endl;
        return;
    }
    
    int d = 0, s = 0;
    cout<<"  "<<src;
    while(true)
    {
        int loc = search(src, s, dst[d]);
        if(loc<0)
        {
            cout<<"  Invalid Input "<<endl;
            return;
        }
        for(int i=loc;i>s;i--)
            swap(src[i], src[i-1]);   
        s++;
        d++;
        cout<<" ----> "<<src;
        if(s == src.length() || src == dst)
            break;
    }
    cout<<endl;
}

int main()
{
    string src, dst;
    
    cout<<"  Enter source      :- ";
    cin>>src;
    
    cout<<"  Enter destination :- ";
    cin>>dst;
    
    pathSrc2Dst(src, dst);
    return 0;
}

bubble sort!!