Table of contents

Introduction

Problem Statement

2.1.

Intuition

2.2.

Algorithm

Implementation in C++

Complexity Analysis

4.1.

Time Complexity

4.2.

Space Complexity

Frequently Asked Questions

5.1.

What is a String?

5.2.

Is string a primitive or a derived type?

5.3.

How do we append to a string?

5.4.

Is string mutable or immutable?

Conclusion

Last Updated: Mar 27, 2024

Easy

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

Author Upendra Prasad Mahto

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

Either it is an Online Assessment or a face-to-face interview. Both are incomplete without Backtracking. The basic concept of Backtracking remains the same, yet many questions are framed on this topic. Today we will see one such question to enrich your concepts about Backtracking, i.e., Minimize swaps of pairs of characters required required required such that no two adjacent characters in the string are the same.

But before preceding this, let’s see what Backtracking is.

Backtracking is a class of algorithms used for finding solutions to some computational problems or notably constraint satisfaction problems. We can also say that it is a technique for finding all the solutions to a given problem by rejecting the solutions that do not satisfy the given constraint.

You can also refer to the article, Introduction to Backtracking to know more about Backtracking.

Now let's discuss the problem statement in detail.

Problem Statement

You have been given a string. You have to find the minimum number of pairs of characters that need to be swapped such that after swapping, no two adjacent characters are the same. If it's not possible, then return '-1'.

Let's understand the problem. Minimize swaps of pairs of characters required by the following example.

Input

'STR’= EWEEHF

Output:

Explanation

If we swap the 3rd and 6th characters in the string, we will have "EWFEHE." There are no two adjacent characters in this string that are the same. It took us one swap. Thus, this is our answer.

Intuition

As we have to find the minimum number of operations required, we can generate all possible combinations and check which of them takes the minimum functions.

But how are we going to create that?

Backtracking? Yes.

Refer to this library, Backtracking for more information.

Let's look at the algorithm we used to solve the problem of Minimize swaps of pairs of characters required

Algorithm

We will create a function, let's say minSwaps() which will take four arguments, namely the 'STR' (given string), 'ANS' (Final answer, initialized to INT_MAX), 'TEMP' (Swaps required in the particular recursive call), and 'RES' which will keep track of the index.

In the function, We will first check if the string contains any adjacent characters which are the same. If they are not the same, then we will update the value of ANS as min(ANS, TEMP). We will iterate over the string using the variable 'i' from 'RES' to 'LEN' (Length of the string). Now we will perform the following operations.

We will use a variable 'j' to iterate from i+1 to 'LEN,' then we will swap the characters at position' i' and 'j' and then call the function minSwaps(). But this time, we will increment the value of 'RES' to 'i’+1 and 'TEMP' to 'TEMP’+1 as we have made one swap.
Now we will backtrack, i.e., swap the 'i's and 'j' characters again.

After the complete string is traversed, our final answer will be stored in 'ANS.' If the value of 'ANS' after the process is 'INT_MAX,' then we will print '-1'; otherwise, we will print the value of 'ANS.'

Let's see the implementation of the problem. Minimize swaps of pairs of characters required.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
// It is used to check if the string contains any pair of adjacent characters that are the same. It returns a boolean value.
bool check(string& str)
{
    for (int i = 1; i < str.length(); i++) {
        if (str[i - 1] == str[i]) {
            return false;
        }
    }
    return true;
}

//This function is used to find the minimum number of swaps of pairs of characters required to make all pairs of adjacent characters different.
void minSwapsRequired(string& str, int& ans,int swaps = 0, int res = 0){
    int n=str.length();

    if (check(str)){
        ans = min(ans, swaps);
    }
    for(int i = res;i < n; i++){
        for(int j=i+1; j < n;j++){
            swap(str[i], str[j]);
            minSwapsRequired(str, ans,swaps + 1, i + 1);
            swap(str[i], str[j]);
        }
    }
}


//In the main function, we call the minSwapsRequired function and store the minimum number of swaps required in a variable.
int main()
{
    string str = "EWEEHF";
    int ans = INT_MAX;
    minSwapsRequired(str, ans);
    if (ans == INT_MAX)
        cout<<"-1";
    else
        cout<<ans;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input:

EWEEHF

Output:

Complexity Analysis

Time Complexity

The time complexity of the problem is O(N ^ 3 * 2 ^ N), where N is the length of the string.

Here, 2 ^ N time will be taken by Backtracking, whereas we are looping thrice inside the program, making the time complexity O(N ^ 3) and overall time complexity O(N ^ 3 * 2 ^ N).

Space Complexity

The space complexity of the problem is O(1).

Now, let's see some FAQs related to the problem, Minimize swaps of pairs of characters required.

Check out this article - Balanced Parentheses

Frequently Asked Questions

What is a String?

A string is a data structure implemented as an array data structure of bytes. It stores a sequence of elements, typically characters, using some character encoding.

Is string a primitive or a derived type?

A string is a derived data type.

How do we append to a string?

We can use the '+' operator to append two strings to create a new string.

Is string mutable or immutable?

A string object always represents the same string. Therefore it is an example of an immutable type.

Conclusion

We have discussed the problem, Minimize swaps of pairs of characters required such that no two adjacent characters in the string are the same. We have also addressed the problem statement with the algorithm. At last, we have seen their time complexity and some related FAQs.

After reading about the problem, Minimize swaps of pairs of characters required such that no two adjacent characters in the string are the same, are you not feeling excited to read/explore more articles on Data Structures and Algorithms? Don't worry; Coding Ninjas has you covered. See Graph, Binary Tree, BFS vs DFS, DFS Algorithm, Check for Balanced Parentheses in an Expression, and Stack to learn.