Проверьте, является ли какая-либо перестановка данной строки лексикографически большей, чем другая заданная строка

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

Для заданных двух строк str1 и str2 одинаковой длины N задача состоит в том, чтобы проверить, существует ли какая-либо возможная перестановка в любой из заданных строк, такая, что каждый символ одной строки больше или равен каждому символу другой строки при соответствующих индексы. Возвращает true, если перестановка существует, иначе false.

Пример:

Input: str1 = “adb”, str2 = “cda”
Output: true
Explanation: After permutation str1 = “abd” and str2 = “acd”, so every character from str2 is greater or equals to every character from s1.

Input: str1 = “gfg”, str2 = “agd”
Output: true

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

  • Преобразование заданных строк в массив символов
  • Сортировать оба массива символов
  • Теперь выполните итерацию по этим массивам и проверьте, больше ли каждый символ одного массива или равен соответствующему символу в другом массиве.
  • Если найдено лексикографически большее, выведите true, иначе false.

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

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

Подход 2. Описанный выше подход можно оптимизировать с помощью карты частот для заданных строк.

  • Сделать карту частот для обеих заданных строк
  • Создайте переменные count1 и count2 , чтобы указать совокупную частоту соответствующих строк.
  • Переберите карту частот и проверьте, больше ли значение для какой-либо строки, чем другое или нет.
  • Если да, выведите true. В противном случае выведите false.

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

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

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