Minimum Operations To Make Strings Same

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
5 upvotes
Asked in companies
UberDaffodil Software

Problem statement

Given two strings ‘initial’ and ‘final’ , where ‘initial’ is the initial string and ‘final’ is the final string. Each state will contain ‘a’,’b’ and only one empty slot represented by ‘_’. Your task is to transform the initial string into the final string with the minimum number of operation.

Allowed operations are:

1. You can swap empty character with any adjacent character. (For example, ‘aba_ab’ can be converted into ‘ab_aab’ or ‘abaa_b’).

2. You can swap empty character with next to the adjacent character only if the adjacent character is different from next to the adjacent character. (For example, ‘aba_ab’ can be converted into ‘a_abab’ or ‘ababa_’, but ‘ab_aab’ cannot be converted to ‘abaa_b’ because ‘a’ cannot jump over ‘a’).
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘2*T’ lines represent the ‘T’ test cases.

The first line of each test case consists of a string ‘initial’ denoting the initial string.

The second line of each test case consists of a string ‘final’ denoting the final string.
Output Format : 
For each test case, print a single integer denoting the minimum number of operations to convert the initial string to the final string.
Note : 
1. Do not print anything, it has already been taken care of. Just implement the given function.

2. The string characters consist of ‘a’ ‘b’ and one  ‘_’.

3. Length of the initial string is equal to the length of the final string.
Constraints : 
1 <= T <= 25
1<= length(initial), length(final) <= 10

Time limit: 1 sec
Sample Input 1 :
2
a_b
ab_
aba_a
_baaa
Sample Output 1 :
1
2
Explanation Of Sample Input 1 :
Test Case 1:



The initial string is: a_b
The final string is ab_

We can clearly see that using the first operation i.e swapping the second and third character we can get the final string ab_.

Therefore we return 1.

Test Case 2: 

The initial string is: aba_a
The final string is: _baaa

We need 2 operations to change the initial string to final string i.e :
(Consider 0 based indexing)
1.Swap index 2 and index 3 (Allowed since they are adjacent)

After the operation, the string is: ab_aa

2. Swap index 0 and index 2 ( Allowed since ‘_’ is at index 2 and the elements at index 1 and 0 are different.
After the operation, the string is: _baaa

Which is the final string.
Hence the minimum of 2 operations are needed.
Sample Input 2 :
2
ab_bba
bbbaa_
aa_ab
b_aaa
Sample Output 2 :
6
6
Hint

Use a Breadth-first search to find the optimal answer.

Approaches (1)
BFS Approach
  • We need to convert our initial string into the final string by a series of given operations.
  • We can think of each operation as a change in the string and we can think of these strings as nodes in a graph.
  • We make a map which stores strings and the minimum number of moves to convert the initial string into the current string.
  • We start from the initial string and connect it with the strings which can it can be converted to in one operation. For example let initial string be ‘a_ba’ now all the possible strings in one operation are: ‘_aba’ ,’ab_a’ , ‘aba_’(as shown in graph). So we connect the initial string to the above-mentioned strings with an edge.
  • We do the same for all nodes of the graph. Eventually, we will have our final string as a node.
  • Now since it is always possible to convert the initial string to the final string, we just need to find the shortest path in our graph from the initial string to the final string.
  • This can be easily done using a BFS or a breadth-first search.

For example, let us take the initial string ‘a_ba’ and final string ‘baa_’  a small part of the graph will look like this:

The lines in red signify the shortest path. We can clearly see that we need 3 operations to convert the initial string to the final string.

Keeping all this in mind we can design the following approach:

  • First of all, we find the current position of the ‘_’ and store it.
  • Then we create a map 'nodes' which stores the string and minimum number of operations to reach that string from the initial string
  • Apply the BFS over the string and an element of the queue used for BFS will contain the pair (str, pos) where pos is the position of _ in the string str.
  • Let ‘Initial’ be the initial string and ‘Final’ be the final string.
  • Also, maintain a map ‘nodes’ which will store the string as key and the minimum moves to get to the string as value.
  • For every string str from the queue, generate a new string tmp based on the four conditions given and update the nodes map as nodes[tmp] = nodes[str] + 1.
  • Repeat the above steps until the queue is empty or the required string is generated i.e. tmp == final
  • If the required string is generated then return nodes[str] + 1 which is the minimum number of operations required to change Initial to Final.
Time Complexity

O(4^N), Where ‘N’ denotes the number of elements present in the string.

 

In the worst case, we can have 4 unique possible strings after every operation, therefore the number of nodes in the graph will be 4^N. Since BFS takes linear time, the time complexity will be 4^N.

Space Complexity

O(N*4^N). Where ‘N’ denotes the number of elements present in the string.

 

Since we maintain a map of strings and in the worst case we can have 4^N unique strings, therefore, the space complexity will be N*4^N.

Code Solution
(100% EXP penalty)
Minimum Operations To Make Strings Same
Full screen
Console