Given N strings in the form of array str, each of length M and containing only characters ‘a‘ and ‘b‘. The task is to find the count of minimum number of Inversion Pairs possible in the resultant strings formed by concatenating all N strings in any order, without changing the order of any individual string.
An Inversion Pair in a string S is a pair of indices (i,j) such that i<j and Si = ‘b’, Sj = ‘a’.
For example, the string S= “abababbbb” contains 3 inversions : (2,3), (2,5), (4,5).
Examples:
Input: N = 3 , M = 2, str = {“ba” , “aa” , “ab”}
Output: 2
Explanation: If we concatenate the strings in order s2 + s1 + s3 = “aabaab” , then the inversion pair will be at (3, 4) and (3 , 5)
Input: N = 2 , M = 2, str = {“b” , “b”}
Output: 0
Approach: This question can be solved by the Greedy Algorithm and the approach should be to keep the string with a higher count of character ‘b‘ at the right end.
Follow the below steps to solve the problem:
- Take a vector of strings of size n to receive the input.
- Sort the vector of strings using the comparators based on the count of ‘b‘ in a particular string.
- Take an empty string, Let us say res = “”.
- After that traverse, the sorted vector, add the current string to the string res.
- Traverse the string res and keep the count of occurrences of ‘b’ and whenever you encounter the character ‘a’ add the number of ‘b’ seen so far to the ans variable because with that ‘a’ you can make pairs up to a number of ‘b’ seen so far.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Comparator function to sort the vectors// of stringsbool cmp(string& s1, string& s2){ return count(s1.begin(), s1.end(), 'b') < count(s2.begin(), s2.end(), 'b');}// Function to find the inversion pairsint findInversion(vector<string> arr, int N, int M){ // Sort the vector sort(arr.begin(), arr.end(), cmp); string res = ""; // Concatenate the strings for (int i = 0; i < N; i++) { res = res + arr[i]; } // Count number of 'b' int cnt = 0; // Count the total number of // inversion pairs in the entire int inversionPairs = 0; // N*M = new size of the concatenated string for (int i = 0; i < N * M; i++) { // If the current character is 'b' // then increase the count of cnt if (res[i] == 'b') { cnt += 1; continue; } // Add the cnt because that number of // pairs can be formed to that 'a' else { inversionPairs = inversionPairs + cnt; } } return inversionPairs;}// Driver Functionint main(){ int N = 3, M = 2; vector<string> arr = { "ba" , "aa" , "ab" }; // Calling the function int ans = findInversion(arr, N, M); // Printing the answer cout << ans << "\n"; return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;class GFG { // Function to find the inversion pairs public static int findInversion(List<String> arr, int N, int M) { String res = ""; // Concatenate the strings for (int i = 0; i < N; i++) { res = res + arr.get(i); } // Count number of 'b' int cnt = 0; // Count the total number of // inversion pairs in the entire int inversionPairs = 0; // N*M = new size of the concatenated string for (int i = 0; i < N * M; i++) { // If the current character is 'b' // then increase the count of cnt if (res.charAt(i) == 'b') { cnt += 1; continue; } // Add the cnt because that number of // pairs can be formed to that 'a' else { inversionPairs = inversionPairs + cnt; } } return inversionPairs; } public static void main(String[] args) { int N = 3, M = 2; List<String> arr = new ArrayList<String>(); arr.add("ba"); arr.add("aa"); arr.add("ab"); // Calling sort with Comparator function to sort the // vectors of strings Collections.sort(arr, new Comparator<String>() { @Override public int compare(final String s1, String s2) { int cnts1 = 0; for (int i = 0; i < s1.length(); i++) { if ('b' == s1.charAt(i)) { cnts1++; } } int cnts2 = 0; for (int i = 0; i < s2.length(); i++) { if ('b' == s2.charAt(i)) { cnts2++; } } int ans = -1; if (cnts1 > cnts2) ans = 1; return ans; } }); // Calling the function and passing the sorted array // in it int ans = findInversion(arr, N, M); // Printing the answer System.out.println(ans); }}// This code is contributed by akashish__ |
Python3
# Python program for the above approach# Comparator function to sort the vectors# of stringsdef cmp(s): s1 = s[0] s2 = s[1] b_in_s1 = 0 b_in_s2 = 0 for i in s1: if (i == 'b'): b_in_s1 += 1 for i in s2: if (i == 'b'): b_in_s2 += 1 if(b_in_s1 == b_in_s2): return 0 return 1 if b_in_s1 - b_in_s2 else -1;# Function to find the inversion pairsdef findInversion(arr, N, M): # Sort the vector #arr.sort(key=cmp); arr.sort(key=cmp) res = ""; # Concatenate the strings for i in range(N): res = res + arr[i]; # Count number of 'b' cnt = 0; # Count the total number of # inversion pairs in the entire inversionPairs = 0; # N*M = new size of the concatenated string for i in range(N * M): # If the current character is 'b' # then increase the count of cnt if (res[i] == 'b'): cnt += 1; continue; # Add the cnt because that number of # pairs can be formed to that 'a' else: inversionPairs = inversionPairs + cnt; return inversionPairs;# Driver FunctionN = 3M = 2;arr = ["ba", "aa", "ab"];# Calling the functionans = findInversion(arr, N, M);# Printing the answerprint(ans);# This code is contributed by saurabh_jaiswal. |
C#
using System;using System.Collections;using System.Collections.Generic;public class GFG { // Comparator function to sort the vectors // of strings public static int cmp(string s1, string s2) { int cnts1 = 0; for (int i = 0; i < s1.Length; i++) { if ('b' == s1[i]) { cnts1++; } } int cnts2 = 0; for (int i = 0; i < s2.Length; i++) { if ('b' == s2[i]) { cnts2++; } } int ans = 0; if (cnts1 > cnts2) ans = 1; return ans; } // Function to find the inversion pairs public static int findInversion(List<string> arr, int N, int M) { // Sort the vector arr.Sort(cmp); string res = ""; // Concatenate the strings for (int i = 0; i < N; i++) { res = res + arr[i]; } // Count number of 'b' int cnt = 0; // Count the total number of // inversion pairs in the entire int inversionPairs = 0; // N*M = new size of the concatenated string for (int i = 0; i < N * M; i++) { // If the current character is 'b' // then increase the count of cnt if (res[i] == 'b') { cnt += 1; continue; } // Add the cnt because that number of // pairs can be formed to that 'a' else { inversionPairs = inversionPairs + cnt; } } return inversionPairs; } static public void Main() { int N = 3, M = 2; List<string> arr = new List<string>(); arr.Add("ba"); arr.Add("aa"); arr.Add("ab"); // Calling the function int ans = findInversion(arr, N, M); // Printing the answer Console.WriteLine(ans); }}// This code is contributed by akashish__ |
Javascript
<script>// Javascript program for the above approach// Comparator function to sort the vectors// of stringsfunction cmp(s1, s2) { let b_in_s1 = 0 let b_in_s2 = 0 for (i of s1) if (i == 'b') b_in_s1++; for (i of s2) if (i == 'b') b_in_s2++; return b_in_s1 - b_in_s2;}// Function to find the inversion pairsfunction findInversion(arr, N, M){ // Sort the vector arr.sort(cmp); let res = ""; // Concatenate the strings for (let i = 0; i < N; i++) { res = res + arr[i]; } // Count number of 'b' let cnt = 0; // Count the total number of // inversion pairs in the entire let inversionPairs = 0; // N*M = new size of the concatenated string for (let i = 0; i < N * M; i++) { // If the current character is 'b' // then increase the count of cnt if (res[i] == 'b') { cnt += 1; continue; } // Add the cnt because that number of // pairs can be formed to that 'a' else { inversionPairs = inversionPairs + cnt; } } return inversionPairs;}// Driver Functionlet N = 3, M = 2;let arr = ["ba", "aa", "ab"];// Calling the functionlet ans = findInversion(arr, N, M);// Printing the answerdocument.write(ans);// This code is contributed by saurabh_jaiswal.</script> |
Output
2
Time Complexity: O(NlogN)
Auxiliary Space: O(N*M)
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!
