Recuento mínimo de pares de inversión posible concatenando N strings binarias en cualquier orden

Dadas N strings en forma de array str , cada una de longitud M y que contiene solo los caracteres ‘ a ‘ y ‘ b ‘. La tarea es encontrar el recuento del número mínimo de pares de inversión posibles en las strings resultantes formadas al concatenar todas las N strings en cualquier orden, sin cambiar el orden de ninguna string individual.

Un par de inversión en una string S es un par de índices (i,j) tales que i<j y Si = ‘b’, Sj = ‘a’ . 

Por ejemplo, la string S= “abababbbb” contiene 3 inversiones: (2,3), (2,5), (4,5).

Ejemplos:

Entrada: N = 3, M = 2, str = { “ba” , “aa” , “ab” }
Salida: 2
Explicación: Si concatenamos las strings en el orden s2 + s1 + s3 = “ aabaab ”, entonces la inversión el par estará en (3, 4) y (3, 5)
 

Entrada: N= 2 , M = 2, str = { “b” , “b” }
Salida: 0

Enfoque:   esta pregunta se puede resolver con el algoritmo Greedy y el enfoque debe ser mantener la string con un mayor número de caracteres ‘ b ‘ en el extremo derecho.

Siga los pasos a continuación para resolver el problema:

1. Tome un vector de strings de tamaño n para recibir la entrada.
2. Ordene el vector de strings utilizando los comparadores en función del recuento de ‘ b ‘ en una string en particular.
3. Tome una string vacía, digamos res = «».
4. Después de ese recorrido, el vector ordenado, agregue la string actual a la string res.
5. Recorra la string res y mantenga el conteo de ocurrencias de   ‘b’  y cada vez que encuentre el carácter ‘a’ agregue el número de ‘b’ visto hasta ahora a la variable ans porque con esa ‘a’ puede hacer pares hasta a número de ‘b’  visto hasta ahora.
    

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Comparator function to sort the vectors
// of strings
bool cmp(string& s1, string& s2)
{
    return count(s1.begin(), s1.end(), 'b')
           < count(s2.begin(), s2.end(), 'b');
}
 
// Function to find the inversion pairs
int 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 that 'a'
        else {
            inversionPairs = inversionPairs + cnt;
        }
    }
    return inversionPairs;
}
 
// Driver Function
int 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;
}

# Python program for the above approach
 
# Comparator function to sort the vectors
# of strings
def 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 pairs
def 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 that 'a'
        else:
            inversionPairs = inversionPairs + cnt;
    return inversionPairs;
 
# Driver Function
N = 3
M = 2;
arr = ["ba", "aa", "ab"];
 
# Calling the function
ans = findInversion(arr, N, M);
 
# Printing the answer
print(ans);
 
# This code is contributed by saurabh_jaiswal.

<script>
// Javascript program for the above approach
 
// Comparator function to sort the vectors
// of strings
function 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 pairs
function 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 that 'a'
        else {
            inversionPairs = inversionPairs + cnt;
        }
    }
    return inversionPairs;
}
 
// Driver Function
let N = 3, M = 2;
let arr = ["ba", "aa", "ab"];
 
// Calling the function
let ans = findInversion(arr, N, M);
 
// Printing the answer
document.write(ans);
 
// This code is contributed by saurabh_jaiswal.
</script>

2

Complejidad temporal: O(NlogN)
Espacio auxiliar:  O(N*M)