Last Updated: 29 Nov, 2020
Minimum Operations To Make Strings Same
Moderate
Asked in companies
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’).
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
Approaches
- 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.