CareerCup

This is a 2 dimensional dynamic programming question. Here is the solution:

dp[i][j] = 
Min{ 
dp[i + 1][j - 1] + 1, if str1[i] = str2[j] && str1[j] = str2[i]
dp[i + 2][j] + 1, if str1[i] = str2[i + 1] && str1[i + 1] = str2[i]
dp[i][j - 2] + 1, if str1[j] = str2[j - 1] && str1[j - 1] = str2[j]
}
In short, it's 
dp[i][j] = Min(dp[i + 1][j - 1], dp[i + 2][j], dp[i][j - 2]) + 1.
Here dp[i][j] means the number of minimum swaps needs to swap str1[i, j] to str2[i, j]. Here str1[i, j] means the substring of str1 starting from pos i to pos j :)

Here is an example like the one in the quesition,
str1 = "aab",
str2 = "baa"

dp[1][1] = 0 since str1[1] == str2[1];
dp[0][2] = str1[0 + 1][2 - 1] + 1 since str1[0] = str2[2] && str1[2] = str2[0].
This is just a simple example, you are sure to be able to solve more complicates ones. 
And I think if you understand the equation above, you are sure to implement it into code which is pretty a two for loop :)

#include <stdio.h>
#include<string.h>
void swap(char *c,char *c1)
{
char temp;
temp=*c;
*c=*c1;
*c1=temp;
}
int main(void) {
// your code goes here
int count=0,i;
char str[2000],str1[2000];
scanf("%s %s",str,str1);
if(strcmp(str,str1)!=0)
{
for(i=0;i<strlen(str);i++)
{
if(str[i]!=str1[i])
{
if(str[i+1]==str1[i] && i+1<strlen(str))
{
swap(&str[i+1],&str[i]);
count++;
}
else if(str[strlen(str)-1]==str1[i])
{
swap(&str[strlen(str)-1],&str[i]);
count++;
}
else
{
if(str[i+1]!=str[i] && i+1<strlen(str) )
{
if(str[i+1]==str1[i+1])
{
swap(&str1[i+1],&str1[i]);
count++;
}
swap(&str[i+1],&str[i]);
count++;
}
else if(str1[i+1]!=str1[i] && i+1<strlen(str))
{
if(str[i+1]==str1[i+1] && str[i+1]!=str[i])
{
swap(&str[i+1],&str[i]);
count++;
}
swap(&str1[i+1],&str1[i]);
count++;
}
}
if(strcmp(str,str1)==0)
break;
}
}
}
printf("%d",count);
puts(str);
puts(str1);
return 0;
}

#include<stdio.h>
#include<string.h>
void lastSwap( char * str)
{
char temp;
int len=strlen(str);
temp=str[len-1];
str[len-1]=str[0];
str[0]=temp;
}
void conSwap ( char * str)
{
int len=strlen(str),i;
char temp;
for (i=0;i< len-1;i++ )
{
temp=str[i];
str[i]=str[i+1];
str[i+1]=temp;
}
}
int main()
{
char str1[200],str2[200];
int count=0;
printf("enter 2 string");
scanf("%s%s",str1,str2);
if (strlen(str1) != strlen(str2))
{
printf("plz enter equal sized strings");
return;
}
if (!strcmp(str1,str2))
printf("both are already equal");
else
{
while (1)
{
if (!strcmp(str1,str2))
break;
else
{
if (count % 2 == 0)
{
lastSwap(str2);
count++;
}
else
{
conSwap(str2);
count++;
}

}
}
}
printf("required move:%d",count);
return 0;
}

char[] aChar = a.toCharArray();
char[] bChar = b.toCharArray();
char cChar;
if ((a.length() >= 1 && a.length() <= 2000) && a.length() == b.length()) {
if (aChar != bChar) {
for (int i = 0; i < aChar.length; i++) {
for (int j = i + 1; j < aChar.length; j++) {
if (aChar[i] != bChar[i]) {
if (aChar[j] == bChar[i] && j < aChar.length) {
cChar = aChar[j];
aChar[j] = aChar[i];
aChar[i] = cChar;
moves++;
} else if (aChar[aChar.length - 1] == bChar[i]) {
cChar = aChar[aChar.length - 1];
aChar[aChar.length - 1] = aChar[i];
aChar[i] = cChar;
moves++;
} else {
if (aChar[j] != aChar[i] && j < aChar.length) {
if (aChar[j] == bChar[j]) {
cChar = bChar[j];
bChar[j] = bChar[i];
bChar[i] = cChar;
moves++;
}
cChar = aChar[j];
aChar[j] = aChar[i];
aChar[i] = cChar;
moves++;
} else if (bChar[j] != bChar[i]
&& i + 1 < aChar.length) {
if (aChar[j] == bChar[j]
&& aChar[j] != aChar[i]) {
cChar = aChar[j];
aChar[j] = aChar[i];
aChar[i] = cChar;
moves++;
}
cChar = bChar[j];
bChar[j] = bChar[i];
bChar[i] = cChar;
moves++;
}
}
if (aChar == bChar) {
break;
}
}
}
}
}
System.out.println("Minimum number of moves: " + moves);
}

But i think it's still not good.

So i did it. Sorry for taking this log to post it, but here it is:

public int findMinimumStringMovement() {
		int moves = 0;
		char[] aChar = a.toCharArray();
		char[] bChar = b.toCharArray();
		char cChar;

		if (aChar != bChar) {
			for (int i = 0; i < aChar.length; i++) {
				for (int j = i + 1; j < aChar.length; j++) {
					if (aChar[i] != bChar[i]) {
						/*
						 * It checks if some character from the array of aChar
						 * is same as other character from the array of B and if
						 * it's j less then the length of the array. If it's
						 * true, then swap the characters and count moves
						 */
						if (aChar[j] == bChar[i] && j < aChar.length) {
							for (int k = j; k > i; k--) {
								cChar = aChar[k];
								aChar[k] = aChar[k - 1];
								aChar[k - 1] = cChar;
								moves++;
							}
							/*
							 * In other case, if the last character of array
							 * aChar same as the some character of bChar and
							 * vice versa, then we should check if the i is
							 * equal to 0, in that case we swap 1st and last
							 * character of array and count as 1 move else if i
							 * value is less then the value of length of array
							 * divided with 2 then it swaps that character to
							 * the first one and then swaps with last and counts
							 * the moves.
							 */
						} else if (aChar[aChar.length - 1] == bChar[i]) {
							if (i == 0) {
								cChar = aChar[aChar.length - 1];
								aChar[aChar.length - 1] = aChar[i];
								aChar[i] = cChar;
								moves++;
							} else if (i < (aChar.length - 1) / 2) {
								for (int k = i; k > 0; k--) {
									cChar = aChar[k];
									aChar[k] = aChar[k - 1];
									aChar[k - 1] = cChar;
									moves++;
								}
								cChar = aChar[i];
								aChar[i] = aChar[aChar.length - 1];
								aChar[aChar.length - 1] = cChar;
							}
						} else if (bChar[bChar.length - 1] == aChar[i]) {
							if (i == 0) {
								cChar = bChar[bChar.length - 1];
								bChar[bChar.length - 1] = bChar[i];
								bChar[i] = cChar;
								moves++;
							} else if (i < (aChar.length - 1) / 2) {
								for (int k = i; k > 0; k--) {
									cChar = aChar[k];
									aChar[k] = aChar[k - 1];
									aChar[k - 1] = cChar;
									moves++;
								}
								cChar = aChar[i];
								aChar[i] = aChar[aChar.length - 1];
								aChar[aChar.length - 1] = cChar;
								moves++;
							}
							/*
							 * And the last case is if there is no other option,
							 * then we asks if some characters in array with
							 * positions i and j are different and if the j
							 * value is less then length of the array and do the
							 * swap.
							 */
						} else {
							if (aChar[j] != aChar[i] && j < aChar.length) {
								if (aChar[j] == bChar[j]) {
									cChar = bChar[j];
									bChar[j] = bChar[i];
									bChar[i] = cChar;
									moves++;
								}
								cChar = aChar[j];
								aChar[j] = aChar[i];
								aChar[i] = cChar;
								moves++;
							} else if (bChar[j] != bChar[i] && j < aChar.length) {
								if (aChar[j] == bChar[j]
										&& aChar[j] != aChar[i]) {
									cChar = aChar[j];
									aChar[j] = aChar[i];
									aChar[i] = cChar;
									moves++;
								}
								cChar = bChar[j];
								bChar[j] = bChar[i];
								bChar[i] = cChar;
								moves++;
							}
						}
						/*
						 * At the end, if arrays are equal, then it is done.
						 */
						if (aChar == bChar) {
							break;
						}
					}
				}
			}
		}
		return moves;
	}

This code gives wrong answer for the below test case
String str1="aaaaaaaab";
String str2="abaaaaaaa";

Hi,

I was trying to solve this problem but according to me, none of the codes or the dp states worked out. Can someone precisely point out the correct solution to it?