Максимальное количество строк, которые нужно выбрать, чтобы было большинство символов

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

Учитывая массив A[] из N строк символов нижнего регистра, задача состоит в том, чтобы найти максимальное количество строк, такое, что один символ имеет большинство, т. е. появление одного символа во всех строках больше, чем все остальные символы вместе взятые.

Примеры:

Input: A[] = {“aba”, “abcde”, “aba”}
Output: 2
Explanation: On choosing {“aba”, “aba”}, the occurrence of character ‘a’ is 4 and the occurrence of rest of the characters is 2, which is less than 4. So, a maximum of 2 strings can be chosen.

Input: A[] = {“bzc”, “zzzdz”, “e”}
Output: 3
Explanation:  All the strings can be chosen, where ‘z’ has the majority.

Подход: у этой проблемы есть жадное решение. Идея состоит в том, чтобы рассмотреть все символы нижнего регистра от 'a' до 'z' и для каждого символа найти максимальное количество строк, которые можно выбрать, чтобы вхождение этого символа было больше, чем все остальные символы вместе взятые. Максимум из них будет ответом. Теперь основная проблема заключается в том, как найти максимальное количество строк, чтобы один конкретный символ имел большинство, для решения этой проблемы используйте жадный алгоритм. Идея состоит в том, чтобы найти максимальное количество строк для определенного символа 'ch', попытаться выбрать строки, в которых встречается наибольшее количество 'ch' по сравнению с появлением всех других символов, т.е. строки, в которых ( вхождение 'ch' – вхождение всех остальных символов) максимально , чтобы в будущем можно было добавить больше строк.

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

  • Определите функцию CalDif(string s, char ch) и выполните следующие задачи:
    • Инициализируйте переменные chcount как 0 , чтобы сохранить количество этого символа, и othercount как 0 , чтобы сохранить количество других символов.
    • Пройдите строку s , используя переменную x , и выполните следующие задачи:
      • Если символом в текущей позиции является ch, то увеличьте значение chcount на 1 , в противном случае увеличьте значение othercount на 1.
    • Возвращает разницу между chcount и othercount.
  • Инициализируйте переменную ans и присвойте 0 , она сохранит окончательный ответ.
  • Переберите диапазон символов нижнего регистра [a, z], используя переменную i , и выполните следующие шаги:
    • Инициализировать вектор arr[] длины N , где arr[i] будет хранить (вхождение ch — вхождение всех остальных символов) для i-й строки.
    • Запустите цикл от i=0 до N-1
      • Для i -й строки вычислить (вхождение ch – появление всех остальных символов) с помощью функции CalDiff(A[i], ch) и присвоить ее arr[i] .
    • Сортировать arr[] в порядке убывания.
    • Инициализируйте две переменные temp и count и присвойте им 0 .
    • Перейдите массив arr[] и выполните temp += arr[i] и count++ , где i начинается с 0 , пока temp <= 0 .
    • Установите максимальное значение ans для ans и count .
  • После выполнения вышеуказанных шагов выведите значение ans в качестве ответа.

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

Временная сложность: O(N * |s|), где |s| максимальная длина строки.
Вспомогательное пространство: O(N)

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