Minimize swaps of pairs of characters required such that no two adjacent characters in the string are same

Minimize swaps of pairs of characters required such that no two adjacent characters in the string are same

Given a string S consisting of N characters, the task is to find the minimum number of pairs of characters that are required to be swapped such that no two adjacent characters are the same. If it is not possible to do so, then print “-1”.

Examples:

Input: S = “ABAACD”
Output: 1
Explanation: Swapping S[3] and S[4] modifies the given string S to “ABACAD”. Since no two adjacent characters are the same, the minimum number of operations required is 1.

Input: S = “AABA”
Output: -1

Approach: The given problem can be solved by using Backtracking. The idea is to generate all possible combinations of swapping of a pair of indices and then if the string is generated having no adjacent characters same with minimum swap, then print that minimum number of swaps operations performed. Follow the steps below to solve the problem:

• Define a function minimumSwaps(string &str, int &minimumSwaps, int swaps=0, int idx) and perform the following operations:
  • If the adjacent characters of the string str are different then update the value of minimumSwaps to the minimum of minimumSwaps and swaps.
  • Iterate over the range [idx, N] using the variable i and performing the following operations:
    • Iterate over the range [i + 1, N] using the variable j and performing the following operations:
      • Swap the characters at positions i and j in string S.
      • Call for the function minimumSwaps(str, minimumSwaps, swaps+1, i + 1) to find other possible pairs of swapping to generate the resultant string.
      • Swap the characters in positions i and j in the string S.
• Initialize the variable, say ansSwaps as INT_MAX to store the count of minimum swaps required.
• Call the function minimumSwaps(str, ansSwaps) to find the minimum number of swaps required to make all the adjacent characters different.
• After completing the above steps, if the value of ansSwaps is INT_MAX, then print -1. Otherwise, print the value of ansSwaps as the resultant minimum swaps.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    bool check(string& S) {          for (int i = 1; i < S.length(); i++) {                              if (S[i - 1] == S[i]) {             return false;         }     }             return true; }    void minimumSwaps(string& S, int& ansSwaps,                   int swaps = 0, int idx = 0) {               if (check(S)) {         ansSwaps = min(ansSwaps, swaps);     }             for (int i = idx;          i < S.length(); i++) {            for (int j = i + 1;              j < S.length(); j++) {                                          swap(S[i], S[j]);             minimumSwaps(S, ansSwaps,                          swaps + 1, i + 1);                                          swap(S[i], S[j]);         }     } }    void findMinimumSwaps(string& S) {                  int ansSwaps = INT_MAX;                  minimumSwaps(S, ansSwaps);             if (ansSwaps == INT_MAX)         cout << "-1";     else         cout << ansSwaps; }    int main() {     string S = "ABAACD";     findMinimumSwaps(S);        return 0; }

Time Complexity: O(N³*2^N)
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets