Given a string S of length N, consisting of only lowercase English characters, the task is to find the minimum number of adjacent swaps required to group the same characters together.
Examples:
Input: S = “cbabc”
Output: 4
Explanation:
Swap characters S[0] to S[1]. Therefore, S = “bcabc”.
Swap characters S[1] to S[2]. Therefore, S = “bacbc”.
Swap characters S[2] to S[3]. Therefore, S = “babcc”.
Swap characters S[1] to S[2]. Therefore, S = “bbacc”.
Hence, the total swaps required is 4.Input: S = “abcd”
Output: 0
Explanation:
All characters are distinct. Hence, no swapping is required.
Approach: The idea is to store the indices of each character. Then, for each character, find the adjacent absolute differences and add them to the answer. Follow the steps below to solve the problem:
- Initialize a 2D vector arr[], where vector arr[i] will store the indices of character (i + ‘a’) and a variable answer initialized to 0.
- Iterate the given string over the range [0, N – 1].
- Add index i to arr[S[i] – ‘a’].
- After traversing the string, traverse the 2D vector arr[] from i = ‘a’ to ‘z’.
- For each character i, find the absolute adjacent differences of the indices of character i present in that vector and add them to the answer.
- After traversing the 2D vector, print the answer as the minimum number of 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 find minimum adjacent// swaps required to make all the// same character adjacentint minSwaps(string S, int n){ // Initialize answer int swaps = 0; // Create a 2D array of size 26 vector<vector<int> > arr(26); // Traverse the string for (int i = 0; i < n; i++) { // Get character int pos = S[i] - 'a'; // Append the current index in // the corresponding vector arr[pos].push_back(i); } // Traverse each character from a to z for (char ch = 'a'; ch <= 'z'; ++ch) { int pos = ch - 'a'; // Add difference of adjacent index for (int i = 1; i < arr[pos].size(); ++i) { swaps += abs(arr[pos][i] - arr[pos][i - 1] - 1); } } // Return answer return swaps;}// Driver Codeint main(){ // Given string string S = "abbccabbcc"; // Size of string int N = S.length(); // Function Call cout << minSwaps(S, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find minimum adjacent// swaps required to make all the// same character adjacentstatic int minSwaps(String S, int n){ // Initialize answer int swaps = 0; // Create a 2D array of size 26 @SuppressWarnings("unchecked") Vector<Integer> []arr = new Vector[26]; for(int i = 0; i < arr.length; i++) arr[i] = new Vector<Integer>(); // Traverse the String for(int i = 0; i < n; i++) { // Get character int pos = S.charAt(i) - 'a'; // Append the current index in // the corresponding vector arr[pos].add(i); } // Traverse each character from a to z for(char ch = 'a'; ch <= 'z'; ++ch) { int pos = ch - 'a'; // Add difference of adjacent index for(int i = 1; i < arr[pos].size(); ++i) { swaps += Math.abs(arr[pos].get(i) - arr[pos].get(i - 1) - 1); } } // Return answer return swaps;}// Driver Codepublic static void main(String[] args){ // Given String String S = "abbccabbcc"; // Size of String int N = S.length(); // Function Call System.out.print(minSwaps(S, N));}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach# Function to find minimum adjacent# swaps required to make all the# same character adjacentdef minSwaps(S, n): # Initialize answer swaps = 0 # Create a 2D array of size 26 arr = [[] for i in range(26)] # Traverse the string for i in range(n): # Get character pos = ord(S[i]) - ord('a') # Append the current index in # the corresponding vector arr[pos].append(i) # Traverse each character from a to z for ch in range(ord('a'), ord('z') + 1): pos = ch - ord('a') # Add difference of adjacent index for i in range(1, len(arr[pos])): swaps += abs(arr[pos][i] - arr[pos][i - 1] - 1) # Return answer return swaps# Driver Codeif __name__ == '__main__': # Given string S = "abbccabbcc" # Size of string N = len(S) # Function Call print(minSwaps(S, N))# This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approachusing System;using System.Collections.Generic;class GFG{// Function to find minimum// adjacent swaps required // to make all the same // character adjacentstatic int minSwaps(String S, int n){ // Initialize answer int swaps = 0; // Create a 2D array // of size 26 List<int> []arr = new List<int>[26]; for(int i = 0; i < arr.Length; i++) arr[i] = new List<int>(); // Traverse the String for(int i = 0; i < n; i++) { // Get character int pos = S[i] - 'a'; // Append the current index in // the corresponding vector arr[pos].Add(i); } // Traverse each character // from a to z for(char ch = 'a'; ch <= 'z'; ++ch) { int pos = ch - 'a'; // Add difference of // adjacent index for(int i = 1; i < arr[pos].Count; ++i) { swaps += Math.Abs(arr[pos][i] - arr[pos][i - 1] - 1); } } // Return answer return swaps;}// Driver Codepublic static void Main(String[] args){ // Given String String S = "abbccabbcc"; // Size of String int N = S.Length; // Function Call Console.Write(minSwaps(S, N));}}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript program for the above approach// Function to find minimum adjacent// swaps required to make all the// same character adjacentfunction minSwaps(S,n){ // Initialize answer let swaps = 0; // Create a 2D array of size 26 let arr = new Array(26); for(let i = 0; i < arr.length; i++) arr[i] = []; // Traverse the String for(let i = 0; i < n; i++) { // Get character let pos = S[i].charCodeAt(0) - 'a'.charCodeAt(0); // Append the current index in // the corresponding vector arr[pos].push(i); } // Traverse each character from a to z for(let ch = 'a'.charCodeAt(0); ch <= 'z'.charCodeAt(0); ++ch) { let pos = ch - 'a'.charCodeAt(0); // Add difference of adjacent index for(let i = 1; i < arr[pos].length; ++i) { swaps += Math.abs(arr[pos][i] - arr[pos][i-1] - 1); } } // Return answer return swaps;}// Driver Code// Given Stringlet S = "abbccabbcc";// Size of Stringlet N = S.length;// Function Calldocument.write(minSwaps(S, N));// This code is contributed by patel2127</script> |
Output
10
Time Complexity: O(26*N)
Auxiliary Space: O(N)
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!
