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;
}
You can also try this code with Online C++ Compiler
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!
62+ registered