Minimum number of adjacent swaps required to reverse a string

Given a string str, we can reverse the string by just swapping adjacent characters. We need to find the minimum number of moves required to reverse the string, just by swapping adjacent characters. We will implement two methods to find the required solution and provide an explanation and implementation of the code.

ExampleExample

Input1: string str1 = “shkej”

Output: 10

The Chinese translation of

Explanation

is:

Explanation

First, we will move the last character to the first position, which will require 4 swaps, and then the string will become "jshke". Then we will move the 'e' to the second position, which will require 3 swaps. Similarly, for 'k', we need two swaps, while for 'h', only 1 swap is required, and the final answer is 10.

Input2: string str1 = “abace”

Output: 6

The Chinese translation of

Explanation

is:

Explanation

First we will swap the character at the 2nd index and move it to the last index, this will take 2 swaps and the string will become "abcea". Then we swap 'b' for 'e', ​​it will take 2 swaps and the string will become "aceba". Then perform 2 more exchanges to get the final reversed string, which requires a total of 6 exchanges.

The Chinese translation of

Naive Approach

is:

Naive Approach

We've looked at the example above, now let's look at the steps required to implement the correct code.

• First, we will create a function that will take the given string as parameter and will return the minimum number of steps required as the return value.

• In this function we will create a copy of the string and then reverse it to compare with the original string.

• We will create three variables, the first two are used to iterate through the string and the last one is used to store the required number of steps.

• By using a while loop, we will iterate through the given string and continue skipping the number of iterations that the current index value is the same as the reversed string.

• We will then use a while loop to swap adjacent characters until 'j' reaches 'i', and increment the count on each swap.

• Finally, we will return the value of the count and print it out in the main function.

Example

#include <bits/stdc++.h>
using namespace std;
// function to get the minimum number of swaps 
int minSwaps(string str){
   string temp = str;
   reverse(temp.begin(), temp.end()); // reversing the string 
   int i = 0, j = 0;
   int ans = 0;
   int len = str.size();
   while (i <len) {
      j = i;		
      // find the character that is equal to the current element 
      while (str[j] != temp[i]) {
         j++;
      }
      // iterating util the current i is equal to j
      while (i < j) {
         char tempc = str[j];
         str[j] = str[j - 1];
         str[j - 1] = tempc;
         j--;
         ans++;
      }
      i++;
   }
   return ans;
}
int main(){
   string str = "efabc"; // given string     
   // calling the function to find the minimum number of steps required 
   cout<<"The minimum number of steps required to reverse the given string by swapping the adjacent characters is "<<minSwaps(str)<<endl;
   return 0;
}

Output

The minimum number of steps required to reverse the given string by swapping the adjacent characters is 10

Time and space complexity

The time complexity of the above code is O(N^2), where N is the length of the given string. We use nested while loops to give factors of N during the iteration.

The space complexity of the above code is O(N) because we create an extra string there to store the inversion of the given string.

Note - An alternative approach is possible here, but requires the use of very advanced data structures. The concept of this method is that we can start from the last character and check until the first character meets the condition. Then in theory we could move that character to the last position and mark that position as completed and store that value in a high-level data structure.

Then for each character, we will find the same character appearing from behind, which is not yet tagged, and then increase the count to the total number of elements after it minus the number of tagged elements.

in conclusion

In this tutorial, we implemented a code to find the minimum number of steps required to reverse a given string by swapping only adjacent characters. We used nested while loops and reversed the copy of the given string to find the solution. The time complexity of the above code is O(N^2), where N is the size of the string, and the space complexity is O(N).

The above is the detailed content of Minimum number of adjacent swaps required to reverse a string. For more information, please follow other related articles on the PHP Chinese website!