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:
- 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++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if S// contains any pair of// adjacent characters that are samebool check(string& S){ // Traverse the string S for (int i = 1; i < S.length(); i++) { // If current pair of adjacent // characters are the same if (S[i - 1] == S[i]) { return false; } } // Return true return true;}// Utility function to find the minimum number// of swaps of pair of characters required// to make all pairs of adjacent characters differentvoid minimumSwaps(string& S, int& ansSwaps, int swaps = 0, int idx = 0){ // Check if the required string // is formed already if (check(S)) { ansSwaps = min(ansSwaps, swaps); } // Traverse the string S for (int i = idx; i < S.length(); i++) { for (int j = i + 1; j < S.length(); j++) { // Swap the characters at i // and j position swap(S[i], S[j]); minimumSwaps(S, ansSwaps, swaps + 1, i + 1); // Swap for Backtracking // Step swap(S[i], S[j]); } }}// Function to find the minimum number// of swaps of pair of characters required// to make all pairs of adjacent characters differentvoid findMinimumSwaps(string& S){ // Stores the resultant minimum // number of swaps required int ansSwaps = INT_MAX; // Function call to find the // minimum swaps required minimumSwaps(S, ansSwaps); // Print the result if (ansSwaps == INT_MAX) cout << "-1"; else cout << ansSwaps;}// Driver Codeint main(){ string S = "ABAACD"; findMinimumSwaps(S); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ static int ansSwaps ; // Function to check if S// contains any pair of// adjacent characters that are samestatic boolean check(char[] S){ // Traverse the String S for (int i = 1; i < S.length; i++) { // If current pair of adjacent // characters are the same if (S[i - 1] == S[i]) { return false; } } // Return true return true;}// Utility function to find the minimum number// of swaps of pair of characters required// to make all pairs of adjacent characters differentstatic void minimumSwaps(char[] S, int swaps, int idx){ // Check if the required String // is formed already if (check(S)) { ansSwaps = Math.min(ansSwaps, swaps); } // Traverse the String S for (int i = idx; i < S.length; i++) { for (int j = i + 1; j < S.length; j++) { // Swap the characters at i // and j position swap(S,i,j); minimumSwaps(S, swaps + 1, i + 1); // Swap for Backtracking // Step S= swap(S,i,j); } }}static char[] swap(char []arr, int i, int j){ char temp= arr[i]; arr[i]=arr[j]; arr[j]=temp; return arr;} // Function to find the minimum number// of swaps of pair of characters required// to make all pairs of adjacent characters differentstatic void findMinimumSwaps(char[] S){ // Stores the resultant minimum // number of swaps required ansSwaps = Integer.MAX_VALUE; // Function call to find the // minimum swaps required minimumSwaps(S, 0,0); // Print the result if (ansSwaps == Integer.MAX_VALUE) System.out.print("-1"); else System.out.print(ansSwaps);}// Driver Codepublic static void main(String[] args){ String S = "ABAACD"; findMinimumSwaps(S.toCharArray());}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approachimport sysansSwaps = 0# Function to check if S# contains any pair of# adjacent characters that are samedef check(S): # Traverse the String S for i in range(1, len(S)): # If current pair of adjacent # characters are the same if (S[i - 1] == S[i]): return False # Return true return True # Utility function to find the minimum number# of swaps of pair of characters required# to make all pairs of adjacent characters differentdef minimumSwaps(S, swaps , idx): global ansSwaps # Check if the required String # is formed already if (check(S)): ansSwaps = 1+min(ansSwaps, swaps) # Traverse the String S for i in range(idx, len(S)): for j in range(i + 1, len(S)): # Swap the characters at i # and j position swap(S, i, j) minimumSwaps(S, swaps + 1, i + 1) # Swap for Backtracking # Step S = swap(S, i, j) def swap(arr , i , j): temp = arr[i] arr[i] = arr[j] arr[j] = temp return arr # Function to find the minimum number# of swaps of pair of characters required# to make all pairs of adjacent characters differentdef findMinimumSwaps(S): global ansSwaps # Stores the resultant minimum # number of swaps required ansSwaps = sys.maxsize # Function call to find the # minimum swaps required minimumSwaps(S, 0,0) # Print the result if (ansSwaps == sys.maxsize): print("-1") else: print(ansSwaps)S = "ABAACD"findMinimumSwaps(S.split())# This code is contributed by rameshtravel07. |
C#
// C# program for the above approachusing System;public class GFG{ static int ansSwaps ; // Function to check if S// contains any pair of// adjacent characters that are samestatic bool check(char[] S){ // Traverse the String S for (int i = 1; i < S.Length; i++) { // If current pair of adjacent // characters are the same if (S[i - 1] == S[i]) { return false; } } // Return true return true;}// Utility function to find the minimum number// of swaps of pair of characters required// to make all pairs of adjacent characters differentstatic void minimumSwaps(char[] S, int swaps, int idx){ // Check if the required String // is formed already if (check(S)) { ansSwaps = Math.Min(ansSwaps, swaps); } // Traverse the String S for (int i = idx; i < S.Length; i++) { for (int j = i + 1; j < S.Length; j++) { // Swap the characters at i // and j position swap(S,i,j); minimumSwaps(S, swaps + 1, i + 1); // Swap for Backtracking // Step S= swap(S,i,j); } }}static char[] swap(char []arr, int i, int j){ char temp= arr[i]; arr[i]=arr[j]; arr[j]=temp; return arr;} // Function to find the minimum number// of swaps of pair of characters required// to make all pairs of adjacent characters differentstatic void findMinimumSwaps(char[] S){ // Stores the resultant minimum // number of swaps required ansSwaps = int.MaxValue; // Function call to find the // minimum swaps required minimumSwaps(S, 0,0); // Print the result if (ansSwaps == int.MaxValue) Console.Write("-1"); else Console.Write(ansSwaps);}// Driver Codepublic static void Main(String[] args){ String S = "ABAACD"; findMinimumSwaps(S.ToCharArray());}}// This code is contributed by 29AjayKumar. |
Javascript
<script>// javascript program for the above approachvar ansSwaps ; // Function to check if S// contains any pair of// adjacent characters that are samefunction check(S){ // Traverse the String S for (var i = 1; i < S.length; i++) { // If current pair of adjacent // characters are the same if (S[i - 1] == S[i]) { return false; } } // Return true return true;}// Utility function to find the minimum number// of swaps of pair of characters required// to make all pairs of adjacent characters differentfunction minimumSwaps(S, swaps , idx){ // Check if the required String // is formed already if (check(S)) { ansSwaps = Math.min(ansSwaps, swaps); } // Traverse the String S for (var i = idx; i < S.length; i++) { for (var j = i + 1; j < S.length; j++) { // Swap the characters at i // and j position swap(S,i,j); minimumSwaps(S, swaps + 1, i + 1); // Swap for Backtracking // Step S= swap(S,i,j); } }}function swap(arr , i , j){ var temp= arr[i]; arr[i]=arr[j]; arr[j]=temp; return arr;} // Function to find the minimum number// of swaps of pair of characters required// to make all pairs of adjacent characters differentfunction findMinimumSwaps(S){ // Stores the resultant minimum // number of swaps required ansSwaps = Number.MAX_VALUE; // Function call to find the // minimum swaps required minimumSwaps(S, 0,0); // Print the result if (ansSwaps == Number.MAX_VALUE) document.write("-1"); else document.write(ansSwaps);}// Driver Code var S = "ABAACD"; findMinimumSwaps(S.split(''));// This code is contributed by 29AjayKumar </script> |
Output:
1
Time Complexity: O(N3*2N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
