Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Finding minimum moves required for making 2 strings equal

This is a question from one of the online coding challenge (which has completed).
I just need some logic for this as to how to approach.

Problem Statement:
We have two strings A and B with the same super set of characters. We need to change these strings to obtain two equal strings. In each move we can perform one of the following operations:

1. swap two consecutive characters of a string  
2. swap the first and the last characters of a string

A move can be performed on either string.
What is the minimum number of moves that we need in order to obtain two equal strings?

Input Format and Constraints:
The first and the second line of the input contains two strings A and B. It is guaranteed that the superset their characters are equal.

1 <= length(A) = length(B) <= 2000
All the input characters are between 'a' and 'z'


Output Format:
Print the minimum number of moves to the only line of the output

Sample input:
aab
baa

Sample output:
1

Explanation:
Swap the first and last character of the string aab to convert it to baa. The two strings are now equal.

EDIT : Here is my first try, but I'm getting wrong output. Can someone guide me what is wrong in my approach.

int minStringMoves(char* a, char* b) {
    int length, pos, i, j, moves=0;
    char *ptr;
    length = strlen(a);

    for(i=0;i<length;i++) {
        // Find the first occurrence of b[i] in a
        ptr = strchr(a,b[i]);
        pos = ptr - a;

        // If its the last element, swap with the first
        if(i==0 && pos == length-1) {
            swap(&a[0], &a[length-1]);
            moves++;
        }
        // Else swap from current index till pos
        else {
            for(j=pos;j>i;j--) {
                swap(&a[j],&a[j-1]);
                moves++;
            }
        }

        // If equal, break
        if(strcmp(a,b) == 0)
            break;       
   }

   return moves;
}
like image 551
user2725880 Avatar asked Aug 28 '13 15:08

user2725880


People also ask

How do you make two strings equal?

C++ program to check we can make two strings equal by swapping from third string. Suppose we have three strings S, T and U of same length n. For every index i in range 0 to n-1, we must swap U[i] with either S[i] or T[i]. So in total we have performed n swapping operations.

How do you find the minimum number of operations to make the string balanced?

Find the minimum number of operations required to convert the given string to a balanced string. Here, we can replace C with A , TO GET: ABAB , where each character of the string occurs for 2 times. So, the number of minimum operation(s)= 1 .

How do you make two strings equal in Python?

String Comparison. To test if two strings are equal use the equality operator (==). To test if two strings are not equal use the inequality operator (!=)

How do you make an anagram with two strings?

Input: s = "bab", t = "aba" Output: 1 Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s. Example 2: Input: s = "leetcode", t = "practice" Output: 5 Explanation: Replace 'p', 'r', 'a', 'i' and 'c' from t with proper characters to make t anagram of s.


2 Answers

Take a look at this example:

aaaaaaaaab
abaaaaaaaa

Your solution: 8

aaaaaaaaab -> aaaaaaaaba -> aaaaaaabaa -> aaaaaabaaa -> aaaaabaaaa -> 
aaaabaaaaa -> aaabaaaaaa -> aabaaaaaaa -> abaaaaaaaa

Proper solution: 2

aaaaaaaaab -> baaaaaaaaa -> abaaaaaaaa

You should check if swapping in the other direction would give you better result.

But sometimes you will also ruin the previous part of the string. eg:

caaaaaaaab
cbaaaaaaaa

caaaaaaaab -> baaaaaaaac -> abaaaaaaac

You need another swap here to put back the 'c' to the first place.

The proper algorithm is probably even more complex, but you can see now what's wrong in your solution.

like image 69
Selindek Avatar answered Sep 24 '22 04:09

Selindek


The A* algorithm might work for this problem.

The initial node will be the original string.
The goal node will be the target string.
Each child of a node will be all possible transformations of that string.
The current cost g(x) is simply the number of transformations thus far.
The heuristic h(x) is half the number of characters in the wrong position.

Since h(x) is admissible (because a single transformation can't put more than 2 characters in their correct positions), the path to the target string will give the least number of transformations possible.

However, an elementary implementation will likely be too slow. Calculating all possible transformations of a string would be rather expensive.

Note that there's a lot of similarity between a node's siblings (its parent's children) and its children. So you may be able to just calculate all transformations of the original string and, from there, simply copy and recalculate data involving changed characters.

like image 29
Bernhard Barker Avatar answered Sep 21 '22 04:09

Bernhard Barker