Minimize swaps of pairs of characters required such that no two adjacent characters in the string are same | C ++ program for the above approach ; Function to check if S contains any pair of adjacent characters that are same ; Traverse the string S ; If current pair of adjacent characters are the same ; Return true ; Utility function to find the minimum number of swaps of pair of characters required to make all pairs of adjacent characters different ; Check if the required string is formed already ; Traverse the string S ; Swap the characters at i and j position ; Swap for Backtracking Step ; Function to find the minimum number of swaps of pair of characters required to make all pairs of adjacent characters different ; Stores the resultant minimum number of swaps required ; Function call to find the minimum swaps required ; Print the result ; Driver Code
#include <bits/stdc++.h> NEW_LINE 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 ; }