Лексикографически самая большая строка, образованная путем выбора слов из данного предложения в соответствии с заданным шаблоном.

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

Для данного предложения S и строки B с различными символами найдите строку, соединив слова S в соответствии с заданными условиями:

  • Выберите слово из S , если
    • Он имеет как минимум длину (B)/2 символа из строки B или
    • Имеющий хотя бы один символ из строки B и лексикографически отсортированный по возрастанию.
  • Сформированная строка должна быть лексикографически самой большой строкой.

Примеры:

Input: S = “peek geek suv”, B = “ekps”
Output: suvpeekgeek
Explanation: “suv” has one character from B and sorted in increasing order.
Whereas “peek” and “geek” has length(B)/2 characters.

Input: S = “peek fit and run”, B = “ekta”
Output: peekfit  

Наивный подход : задачу можно решить, сохранив слово строки S и строки B в наборе и сравнив их, если они равны, но для этого потребуется более одного набора, что требует дополнительного времени и места.

Временная сложность: O(N * logN), где N — общее количество символов в S.
Вспомогательное пространство: O(N)

Эффективный подход: лучший подход — использовать карту. Следуя шагам, указанным ниже:

  • Сохраните частоту символов B в неупорядоченной карте и сравните со строками массива S .
  • Если в слове строки S есть два символа, добавьте их в выходную строку.
  • Если присутствует только один символ, проверьте, отсортирован ли он в порядке лексикографического возрастания.
  • Если да, добавьте его в выходную строку.
  • Расположите выходную строку в лексикографически наибольшей перестановке.

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


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

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