Минимальное количество инверсионных пар, возможное путем объединения N двоичных строк в любом порядке.

Опубликовано: 20 Сентября, 2022

Даны N строк в виде массива str , каждая из которых имеет длину M и содержит только символы ' a ' и ' b '. Задача состоит в том, чтобы найти количество минимально возможных пар инверсии в результирующих строках, образованных конкатенацией всех N строк в любом порядке, без изменения порядка любой отдельной строки.

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).

Примеры:

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

Подход: этот вопрос можно решить с помощью жадного алгоритма. и подход должен заключаться в том, чтобы сохранить строку с большим количеством символов ' b ' в правом конце.

Выполните следующие шаги, чтобы решить проблему:

  1. Возьмите вектор строк размера n для получения входных данных.
  2. Сортируйте вектор строк с помощью компараторов на основе количества ' b ' в конкретной строке.
  3. Возьмите пустую строку, скажем, res = «».
  4. После этого обхода отсортированного вектора добавьте текущую строку к строке res.
  5. Перейдите строку res и сохраните количество вхождений «b», и всякий раз, когда вы сталкиваетесь с символом «a», добавляйте количество «b», увиденное до сих пор, к переменной ans , потому что с этим «а» вы можете создавать пары до a количество 'b' видел до сих пор.

Ниже приведена реализация вышеуказанного подхода:


Временная сложность: O(NlogN)
Вспомогательное пространство: O(N*M)

РЕКОМЕНДУЕМЫЕ СТАТЬИ