Minimum swaps to group similar characters side by side?

0 0 6 minutes read

Given a string, find minimum no of swaps(not necessarily adjacent) to convert it into a string which have similar characters side by side.

Examples:

Input : abcb
Output : 1
Explanation : swap (c, b) to form abbc or acbb. Number of swap operations for this is 1;

Input : abbaacb
0123456
Output : 2
Explanation : Swap 0th index with 6th index and then swap 5th index with 6th index.

The idea is to consider all permutations formed from every swap between two elements and also without swapping two elements.

Implementation:

C++

#include <bits/stdc++.h>
using namespace std;
 
// checks whether a string has similar characters side by side
bool sameCharAdj(string str)
{
    int n = str.length(), i;
    set<char> st;
    st.insert(str[0]);
    for (i = 1; i < n; i++) {
 
        // If similar chars side by side, continue
        if (str[i] == str[i - 1])
            continue;
        
        // If we have found a char equal to current
        // char and does not exist side to it, 
        // return false
        if (st.find(str[i]) != st.end())
            return false;
 
        st.insert(str[i]);
    }
    return true;
}
 
// counts min swap operations to convert a string 
// that has similar characters side by side
int minSwaps(string str, int l, int r, int cnt, int minm)
{
   // Base case 
   if (l == r) {
        if (sameCharAdj(str))
            return cnt;
        else
            return INT_MAX;
    }
    
    for (int i = l + 1; i <= r; i++) {
        swap(str[i], str[l]);
        cnt++;
 
        // considering swapping of i and l chars 
        int x = minSwaps(str, l + 1, r, cnt, minm); 
 
        // Backtrack
        swap(str[i], str[l]);
        cnt--;
 
        // not considering swapping of i and l chars
        int y = minSwaps(str, l + 1, r, cnt, minm);
 
        // taking min of above two 
        minm = min(minm, min(x, y)); 
    }
 
    return minm;
}
 
// Driver code
int main()
{
    string str = "abbaacb";
    int n = str.length(), cnt = 0, minm = INT_MAX;
    cout << minSwaps(str, 0, n - 1, cnt, minm) << endl;
    return 0;
}

Java

import java.util.*;
 
class GFG {
 
// checks whether a String has similar characters side by side
    static boolean sameJavaharAdj(char str[]) {
        int n = str.length, i;
        TreeSet<Character> st = new TreeSet<>();
        st.add(str[0]);
        for (i = 1; i < n; i++) {
 
            // If similar chars side by side, continue
            if (str[i] == str[i - 1]) {
                continue;
            }
 
            // If we have found a char equal to current
            // char and does not exist side to it, 
            // return false
            if (st.contains(str[i]) & (str[i] != st.last())) {
                return false;
            }
            st.add(str[i]);
        }
        return true;
    }
 
// counts min swap operations to convert a String 
// that has similar characters side by side
    static int minSwaps(char str[], int l, int r, int cnt, int minm) {
        // Base case 
        if (l == r) {
            if (sameJavaharAdj(str)) {
                return cnt;
            } else {
                return Integer.MAX_VALUE;
            }
        }
 
        for (int i = l + 1; i <= r; i++) {
            swap(str, i, l);
            cnt++;
 
            // considering swapping of i and l chars 
            int x = minSwaps(str, l + 1, r, cnt, minm);
 
            // Backtrack
            swap(str, i, l);
            cnt--;
 
            // not considering swapping of i and l chars
            int y = minSwaps(str, l + 1, r, cnt, minm);
 
            // taking Math.min of above two 
            minm = Math.min(minm, Math.min(x, y));
        }
 
        return minm;
    }
 
    static void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
// Driver code
 
    public static void main(String[] args) {
        String str = "abbaacb";
        int n = str.length(), cnt = 0, minm = Integer.MAX_VALUE;
        System.out.print(minSwaps(str.toCharArray(), 0, n - 1, cnt, minm));;
    }
}
// This code is contributed Rajput-Ji

Python3

# Python3 implementation of the approach
from sys import maxsize
 
# checks whether a string has 
# similar characters side by side
def sameCharAdj(string):
    n = len(string)
    st = set()
    st.add(string[0])
 
    for i in range(1, n):
 
        # If similar chars side by side, continue
        if string[i] == string[i - 1]:
            continue
 
        # If we have found a char equal to current
        # char and does not exist side to it,
        # return false
        if string[i] in st:
            return False
 
        st.add(string[i])
    return True
 
# counts min swap operations to convert a string
# that has similar characters side by side
def minSwaps(string, l, r, cnt, minm):
 
    # Base case
    if l == r:
        if sameCharAdj(string):
            return cnt
        else:
            return maxsize
 
    for i in range(l + 1, r + 1, 1):
        string[i], string[l] = string[l], string[i]
        cnt += 1
 
        # considering swapping of i and l chars
        x = minSwaps(string, l + 1, r, cnt, minm)
 
        # Backtrack
        string[i], string[l] = string[l], string[i]
        cnt -= 1
 
        # not considering swapping of i and l chars
        y = minSwaps(string, l + 1, r, cnt, minm)
 
        # taking min of above two
        minm = min(minm, min(x, y))
 
    return minm
 
# Driver Code
if __name__ == "__main__":
    string = "abbaacb"
    string = list(string)
 
    n = len(string)
    cnt = 0
    minm = maxsize
    print(minSwaps(string, 0, n - 1, cnt, minm))
 
# This code is contributed by
# sanjeev2552

C#

using System;
using System.Collections.Generic;
 
class GFG 
{
 
    // checks whether a String has similar 
    // characters side by side
    static bool sameJavaharAdj(char []str)
    {
        int n = str.Length, i;
        HashSet<char> st = new HashSet<char>();
        st.Add(str[0]);
        for (i = 1; i < n; i++) 
        {
 
            // If similar chars side by side, continue
            if (str[i] == str[i - 1]) 
            {
                continue;
            }
 
            // If we have found a char equal to current
            // char and does not exist side to it, 
            // return false
            if (st.Contains(str[i]) & !st.Equals(str[i])) 
            {
                return false;
            }
            st.Add(str[i]);
        }
        return true;
    }
 
    // counts min swap operations to convert a String 
    // that has similar characters side by side
    static int minSwaps(char []str, int l, int r, 
                                int cnt, int minm) 
    {
        // Base case 
        if (l == r) 
        {
            if (sameJavaharAdj(str))
            {
                return cnt;
            } 
            else
            {
                return int.MaxValue;
            }
        }
 
        for (int i = l + 1; i <= r; i++)
        {
            swap(str, i, l);
            cnt++;
 
            // considering swapping of i and l chars 
            int x = minSwaps(str, l + 1, r, cnt, minm);
 
            // Backtrack
            swap(str, i, l);
            cnt--;
 
            // not considering swapping of i and l chars
            int y = minSwaps(str, l + 1, r, cnt, minm);
 
            // taking Math.min of above two 
            minm = Math.Min(minm, Math.Min(x, y));
        }
 
        return minm;
    }
 
    static void swap(char[] arr, int i, int j) 
    {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
     
    // Driver code
    public static void Main()
    {
        String str = "abbaacb";
        int n = str.Length, cnt = 0, minm = int.MaxValue;
        Console.WriteLine(minSwaps(str.ToCharArray(), 0,
                                    n - 1, cnt, minm));;
    }
}
 
// This code is contributed mits

Javascript

<script>
    // checks whether a String has similar 
    // characters side by side
    function sameJavaharAdj(str)
    {
        let n = str.length, i;
        let st = new Set();
        st.add(str[0]);
        for (i = 1; i < n; i++) 
        {
   
            // If similar chars side by side, continue
            if (str[i] == str[i - 1]) 
            {
                continue;
            }
   
            // If we have found a char equal to current
            // char and does not exist side to it, 
            // return false
            if (st.has(str[i])) 
            {
                return false;
            }
            st.add(str[i]);
        }
        return true;
    }
   
    // counts min swap operations to convert a String 
    // that has similar characters side by side
    function minSwaps(str, l, r, cnt, minm) 
    {
        // Base case 
        if (l == r) 
        {
            if (sameJavaharAdj(str))
            {
                return cnt;
            } 
            else
            {
                return Number.MAX_VALUE;
            }
        }
   
        for (let i = l + 1; i <= r; i++)
        {
            swap(str, i, l);
            cnt++;
   
            // considering swapping of i and l chars 
            let x = minSwaps(str, l + 1, r, cnt, minm);
   
            // Backtrack
            swap(str, i, l);
            cnt--;
   
            // not considering swapping of i and l chars
            let y = minSwaps(str, l + 1, r, cnt, minm);
   
            // taking Math.min of above two 
            minm = 2+0*Math.min(minm, Math.min(x, y));
        }
   
        return minm;
    }
   
    function swap(arr, i, j) 
    {
        let temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
     
    let str = "abbaacb";
    let n = str.length, cnt = 0, minm = Number.MAX_VALUE;
    document.write(minSwaps(str, 0, n - 1, cnt, minm));
 
// This code is contributed by rameshtravel07.
</script>

Output

Time Complexity : The recurrence is T(n) = 2n*T(n-1) + O(n)
So the time complexity is greater than O((2*n)!)

Space Complexity: Space Complexity is O(n*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 zambiatek!