K-я непересекающаяся подстрока длины M после лексикографической сортировки заданной строки

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

Данный строка str размера N и два целых числа M и K (N делится на M), задача состоит в том, чтобы найти K- ю непересекающуюся подстроку размера M после лексикографической сортировки заданной строки

Примеры:

Input: str = “hwnriw”, M = 3, K = 1
Output: hin
Explanation: Non overlapping substrings of size 3 after sorting are “hin” “rww”. 
So 1st string is “hin” .

Input: str = “xeabcks”, M = 3, K = 1
Output: abc

Наивный подход: основная идея решения проблемы состоит в том, чтобы отсортировать всю строку и после этого найти K-ю непересекающуюся подстроку, которая начинается с индекса (K-1)*M .

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

  • Отсортировать всю строку.
  • Получите начальный индекс подстроки K, как указано ниже.
  • И после этого возьмите подстроку размера M из этого индекса.

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

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

Эффективный подход: проблема может быть эффективно решена с использованием хеширования и суммы префиксов на основе следующей идеи:

There are total (K-1)*M characters before the starting character of the Kth substring. 
So store the frequency of all the characters. Then iterate from the smallest character present in the string and with the help of prefix sum find the first character of the Kth substring.

Это поможет решить задачу в линейной временной сложности.

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

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