Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
The Problem Statement
3.
Explanation
4.
Approach
5.
Algorithm
6.
Program
6.1.
Input
6.2.
Output
6.3.
Time Complexity
6.4.
Space Complexity
7.
Key Takeaways
Last Updated: Mar 27, 2024

Minimum Count of Inversion Pairs Possible by Concatenating N Binary Strings in any Order

Author Ujjawal Gupta
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will discuss a problem based on a Sorting in which we have to find the minimum count of inversion pairs possible by concatenating N-binary strings in any order. Problems based on sorting are widely asked in competitive programming contests and various coding interviews. Here we will discuss the efficient approach to reach our result.

The Problem Statement

You are given an integer ‘M’ and an array of binary strings consisting of characters ‘a’ and ‘b’ only of size ‘N’, where the length of each string is ‘M’. Your task is to find the minimum count of inversion pairs possible by concatenating N-binary strings in any order.

Index (i, j) of the string ‘S’ is called inversion if (i<j) and S[i]=’b’ and S[j]=’a’.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Explanation

Let’s understand the problem statement with the help of the following example:

Suppose you have an array of strings ARR = [“aa” , ”ab”, ”bb”] of size three, and the length of each string is two. After concatenation, there will be a total of six combinations possible:

  • In “aaabbb” the inversion count is 0.
  • In “aabbab” the inversion count is 2.
  • In “abaabb” the inversion count is 2.
  • In “abbbaa” the inversion count is 6.
  • In “bbaaab” the inversion count is 6.
  • In “bbabaa” the inversion count is 8.

Among all possible concatenation, as shown above, “aaabbb” has the minimum inversion pair 0. Hence, “aaabbb” is our result.

Approach

The naive approach to solving the above problem is to Count Inversions pairs in all the possible strings we can create by concatenating the given strings and taking the minimum out of them. If the length of an array is ‘N’, there will be total N-factorial strings possible. Hence, this is not an efficient approach.

The efficient approach is to sort the array based on the count of ‘a’ and ‘b’, bypassing the custom function in the sort() function.

Also see, Euclid GCD Algorithm

Algorithm

  • Create a custom function ‘cmp’, which takes two strings as an argument and returns true if ‘a’ in the 1st string is greater than the count of ‘a’ in the 2nd string. 
  • Call the sort() function and pass the above custom function as a third argument.
  • Create a string variable ‘resultant’.
  • Iterate the vector and append each string in the ‘resultant’ variable.
  • Iterate the resultant variable to count the total number of inversion pairs in the ‘resultant’ variable.

Program

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// Custom comparator function to overload the comparator function.
bool cmp(string &binaryString1, string &binaryString2)
{

   // Create variables to store the count of 'a' in both the strings.
   int count1 = 0, count2 = 0;
   for (int i = 0; i < binaryString1.length(); i++)
   {
       if (binaryString1[i] == 'a')
           count1++;
   }
   for (int i = 0; i < binaryString2.size(); i++)
   {
       if (binaryString2[i] == 'a')
           count2++;
   }

   // Return whether the count of 'a' in 1st string is greater than or equal to the count of 'a' in 2nd string.
   return count1 >= count2;
}

// function to calculate the result.
void getMinimumValue(vector<string> &binaryStringArr)
{
   int n = binaryStringArr.size();
  
   // Sort the vector by passing a custom function.
   sort(binaryStringArr.begin(), binaryStringArr.end(), cmp);

   // Creating string variable to store the final string.
   string resultant;
   for (int i = 0; i < n; i++)
   {
       resultant.append(binaryStringArr[i]);
   }

   // Create variables to store the answer.
   int ans = 0, count = 0;

   for (int i = 0; i < resultant.length(); i++)
   {
       if (resultant[i] == 'a')
       {
           ans += count;
       }
       else
       {
           count++;
       }
   }
   cout << ans;
}

// Main function.
int main()
{
   int n, m;
   cin >> n >> m;
   vector<string> binaryStringArr(n);
   for (int i = 0; i < n; i++)
   {
       cin >> binaryStringArr[i];
   }
   getMinimumValue(binaryStringArr);
   return 0;
}

Input

3 2
aa ab bb

Output

0

Time Complexity

O(N*log(N)), where ‘N’ is the total number of strings. 

As sorting of array of size ‘N’ takes O(N * log(N)) time.

Space Complexity

O(N), where ‘N’ is the total number of strings.

As creating a string of size ‘N’ takes O(N) extra space.

Key Takeaways

We have learned how to create a custom function to sort the vector in this blog. Also, we learned how to pass a custom function in our sort function. 

Recommended problems -

 

If you want to learn more about such exciting topics then head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!

 

Previous article
Find All Words in the Given Sentence that are Lexicographically Increasing and Lexicographically Decreasing
Next article
Bitwise Operators in C/C++
Live masterclass