CareerCup

void main()
{
        char a[] = "ACADBB123";
        char b[] = "DC1BA32BA";
        char temp;
        int n = sizeof(b);
        int j, i = 0;
        while(n > i) {
                        j = i;
                        printf("\n%s",a);
                        while(a[j] != b[i]) {
                                j++;
                        }
                        while(j > i) {
                                temp = a[j];
                                a[j] = a[j-1];
                                a[j-1] = temp;
                                printf("\n%s",a);
                                j--;
                        }
                        i++;
        }
}

(1)Do breath first seach, record each state's parent state during state extension.
(2)When reaching the target state, print the swaps using backtrace.
C++ code:

#include <vector>
#include <string>
#include <utility>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

void backtrace(vector<pair<string,int> >& queue, int parentIndex)
{
    if(parentIndex == -1) return;
    backtrace(queue, queue[parentIndex].second);
    cout << queue[parentIndex].first << "\n";
}
bool extend(vector<pair<string,int> >& queue, int& i, int levelCount, set<string>& record, const string& target)
{
    string s;
    for(; levelCount > 0; --levelCount, ++i){
        s = queue[i].first;
        for(string::size_type k = 1, len = s.size(); k < len; ++k){
            if(s[k] == s[k-1]) continue;

            swap(s[k], s[k-1]);
            if(s.compare(target) == 0){
                backtrace(queue, queue[i].second);
                cout << queue[i].first << "\n";
                cout << target << "\n";
                return false;
            }
            if(record.count(s) == 0){
                queue.push_back(make_pair(s, i));
                record.insert(s);
            }
            swap(s[k], s[k-1]);
        }
    }
    return true;
}
int transform(const string& start, const string& target)
{
    if(start.compare(target) == 0) return 0;

    set<string> record;
    vector<pair<string,int> > queue;
    queue.push_back(make_pair(start, -1));
    record.insert(start);

    int step = 0, i = 0, levelCount = 1;
    while(levelCount > 0){
        ++step;
        if(!extend(queue, i, levelCount, record, target)) break;
        else levelCount = queue.size() - i;
    }

    return step;
}

int main()
{
    string start = "GUM", target = "MUG";
    cout << "steps = " << transform(start, target);

    return 0;
}

If there are no duplicate.
Associate int value characters, may be using hashtable
i.e. first word is GUM so
G = 0
U = 1
M = 2

Then do simple bubble sort on MUG with knowlege of associated int values.

#include<iostream>

using namespace std;

int main()
{
	int arr[10],ent,exp,temp=0;
	cin>>exp;
	for(int i=0;i<10;i++)
		arr[i]=0;
	
	temp=exp;
	while(temp)
	{
		arr[temp%10]++;
		temp=temp/10;
	}
	cin>>ent;
	temp=ent;
	while(temp)
	{
		arr[temp%10]--;
		temp=temp/10;
	}
	int count=0;
	for(int i=0;i<10;i++)
	{
		if(arr[i]!=0)
		count++;
	}
	if(count>1)
		cout<<"Invalid";
	else
		cout<<"Valid";
	
	
	return 0;
}

queue seems to me over kill here is how i would solve

static int Find(char ch, int startIndex, char[] str)
        {
            while (startIndex < str.GetLength(0) && str[startIndex] != ch)
            {
                startIndex++;
            }

            if (startIndex >= str.GetLength(0))
            {
                startIndex = -1;
            }

            return startIndex;
        }

        static void Swap(char[] str, int i, int j)
        {
            char temp = str[i];
            str[i] = str[j];
            str[j] = temp;
            Console.WriteLine("swap {0} {1} {2}", i, j, new string(str));
        }

        static void MoveCharToIndex(char[] str, char ch, int index)
        {
            int foundAt = Find(ch, index, str);

            while (foundAt > index)
            {
                Swap(str, foundAt, foundAt - 1);
                foundAt--;
            }

        }

        static void FindMoves(char[] target, char[] original)
        {
            if (target == null)
            {
                throw new ArgumentException("target");
            }
            if (original == null)
            {
                throw new ArgumentException("original");
            }

            //mush be same length

            if (target.GetLength(0) > 0)
            {

                int i = 0;

                while (i < target.GetLength(0))
                {
                    if (target[i] != original[i])
                    {
                        MoveCharToIndex(original, target[i], i);
                    }
                    i++;
                }

            }

        }

        static void FindMoves(string target, string original)
        {
            FindMoves(target.ToCharArray(), original.ToCharArray());
        }

        public static void Main()
        {
            FindMoves("GUM", "MUG");
            FindMoves("TEHUNOOL", "ONLEHTUO");

        }

char[] s1 = str1.toCharArray();
		char[] s2 = str2.toCharArray();

		System.out.println( Arrays.toString(s1) );
		
		int n = s1.length;
		for( int i = 0;i < n; ++ i ){
			if( s1[i]!=s2[i] ){
				int j = i+1;
				for( ; j < n && s1[j] != s2[i]; ++ j );
				//now s1[j] == s2[i]
				for( ; j > i; -- j ){
					swap( s1, j, j-1 );
					System.out.println( Arrays.toString(s1) );
				}
			}
		}

public static void revert(char arr[],int start,int end,int num){
		if(num>=arr.length/2) return;
		for (int i = end; i>=start; i--) {
			System.err.println(arr);
			char temp=arr[i];
			arr[i]=arr[i-1];
			arr[i-1]=temp;
			//System.err.println(arr);
		}
		for (int i = start; i <end; i++) {
			System.err.println(arr);
			char temp=arr[i];
			arr[i]=arr[i+1];
			arr[i+1]=temp;
		//	System.err.println(arr);
		}
		revert(arr, start+1, end-1,num+1);
	}

import java.util.*;

public class Solution { 

	public static void main(String[] args) { 
		String s = "CGUM";
		String d = "MUCG";
		ArrayList<String> result = swap(s,d);
		for(int i=0;i<result.size();i++){
			System.out.println(result.get(i));
		}
	} 
	
	private static ArrayList<String> swap(String s,String d) { 
		ArrayList<String> result = new ArrayList<String>();
		result.add(s);
		char[] st = s.toCharArray();
		for(int i=0;i<s.length();i++){
			if(st[i]!=d.charAt(i)){
				for(int j=i+1;j<s.length();j++){
					if(st[j] == d.charAt(i)){
						for(int k = j;k>i;k--){
							char temp = st[k];
							st[k] = st[k-1];
							st[k-1] = temp;
							result.add(String.valueOf(st));
						}
					}
				}
			}
		}
		return result;
	} 

}

I use recursive to solve this one base on permutation. Since we can swap 2 consecutive characters in the given String, the program will concatenate the first letter with the rest.
If the given String has length of 0 or 1, then return. Otherwise, make a recursive call to the substring s[1:] . Then add back first character to all possible position

# Using python
def permutation(lst):
    ''' take a list of element and return a list of its permutation'''
    if len(lst) == 0 or len(lst) == 1:
        return [lst]
    else:
        outlst = []
        for first in lst:
            rest = list(lst)
            rest.remove(first)
            for restlst in permutation(rest):
                outlst.append([first]+restlst)
        return outlst

def perString(s):
    lst = []
    retLst =[]
    for char in s:
        lst.append(char)
    ret = permutation(lst)
    for word in ret:
        show = ""
        for char in word:
            show += char
        retLst.append(show)
    return retLst

Result:

>>> perString('GUM')
['GUM', 'GMU', 'UGM', 'UMG', 'MGU', 'MUG']

public static void main(String[] args){
char[] s = "abcdefg".toCharArray();
int n = s.length;
swapchar(s,n);
}
public static void swapchar(char[] s,int n){
int length = s.length;
if(n==0)
{
for(int i =0;i<length;i++)
System.out.print(s[i]);
System.out.println();
}else{
char c;
for(int i =0;i<n-1;i++){
c = s[i];
s[i] = s[i+1];
s[i+1] = c;
for(int j =0;j<length;j++)
System.out.print(s[j]);
System.out.println();
}
n = n-1;
swapchar(s,n);
}
}

public class SwapLetters {
	
	public static void main(String[] args) {
		String s = "ABCD";
		char[] inArray = s.toCharArray();
		for (int i = 0; i < inArray.length; i++) {
			for (int j = 0; j < inArray.length-1-i; j++) {
				char temp = inArray[j];
				inArray[j] = inArray[j+1];
				inArray[j+1] = temp;
				System.out.println(new String(inArray));
			}
		}
	}

}

package practice;

import java.sql.Array;

public class String_swap {
public static void main(String Args[])
{
String source="mug";
String dis=new String();
String target="gum";
String source1=new String();
char[] ar=source.toCharArray();
char[] br=target.toCharArray();
int pos=source.indexOf(target.charAt(0));
char c=target.charAt(0);
System.out.println(ar);
int p=0;
for(int i=0;i<source.length()-1 ;i++)
{
	swap(ar,br,pos,p,c);
	c=target.charAt(i+1);
	pos=source.indexOf(target.charAt(i));
	p=i+1;
	
}
//System.out.println(dis);
}
static char[] swap(char[] ar,char[] br, int pos,int p,char c)
{   char temp1,temp2;
	
	while(ar[p]!=c)
	{
			temp1=ar[pos];
			temp2=ar[pos-1];
			ar[pos-1]=temp1;
			ar[pos]=temp2;
			System.out.println(ar);
			pos--;
	}
	return ar;
	
}
}

void permutate(char str[])
{
     int l = strlen(str);
     if (l ==0 || 1 == l)
        return;
     int i, j;
     for (i = 0; i< l-1;i++)
     {
         for (j = 0; j<l-1; j++)
             if (str[j] !=str[j+1])
             {
                        char c = str[j];
                        str[j] = str[j+1];
                        str[j+1] = c;
                        printf("\n %s", str);
             }
     }
     
}

Written in python 3

def scramble(old, new):
    old = list(old); new = list(new)
    print(''.join(new))
    for j in range(len(old)):
        letter = old[j]
        split1 = new[:j]; split2 = new[j:] 
        location = split2.index(letter) #finds location of ith letter in new word
        for i in reversed(range(1, location + 1)):
            temp = split2[i]
            split2[i] = split2[i-1]
            split2[i-1] = temp
            print(''.join(split1 + split2))
        new = split1 + split2

recursive solution

public static void doAllSteps(char [] chs,int lastPre,int last,String target){
		if (lastPre<0){
			lastPre =chs.length-2;
			last= lastPre +1 ;
		}
		
		char tmp = chs[last];
		chs [last] = chs[lastPre];
		chs[lastPre] = tmp;
		if(target.equals(new String(chs))){
			System.out.println(new String(chs));
			return ;
		}else{
			System.out.println(new String(chs));
		}
		lastPre--;
		last--;
		
		doAllSteps(chs,lastPre,last,target);
		
	}
	
	public static void AllSteps(String src, String target){
		System.out.println(src);
		doAllSteps(src.toCharArray(),target.length()-2,target.length()-1,target);
	}

char[] s1 = "TEHUNOOL".toCharArray();
	char[] s2 = "ONLEHTUO".toCharArray();

	transpose(s1, s2);

     public static void transpose(char[] s1, char[] s2) {

	int i = 0;
	System.out.println(Arrays.toString(s1));
	System.out.println(Arrays.toString(s2) + "\n");
	while (i < s2.length) {
	    if (s2[i] == s1[i]) {
		i++;
		System.out.println(Arrays.toString(s1));
	    } else {
		int j = i;
		while (j < s1.length - 1 && s2[i] != s1[i]) {
		    char temp = s1[j];
		    s1[j] = s1[j + 1];
		    s1[j + 1] = temp;
		    j++;
		}
	    }
	}
	System.out.println("\n" + Arrays.toString(s1));
	System.out.println(Arrays.toString(s2));
    }