Длина строки, образованной повторением каждого символа в диапазоне [L, R] данной строки, умноженной на его лексикографическое значение.

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

Дана строка S длины N и диапазон [L, R] (1 <= L, R <= N). Задача состоит в том, чтобы найти длину строки, образованной повторением каждого символа в диапазоне [L, R] до его лексикографического значения раз.

Примеры:

Input: s = “cbbde”, l = 2, r = 5
Output: 13
Explanation: Resultant String is formed after repeating each character in range [2, 5] as shown below: 
b repeated 2 times
b repeated 2 times
d repeated 4 times
e repeated 5 times
 

Resultant string: ‘bbbbddddeeeee’
Therefore, length of resultant string so formed is 13

Input: s = “xyyz”, l = 1, r = 2
Output:  49

Нативный подход: задачу можно решить, сформировав временную строку, добавив символы , повторяющиеся лексикографически раз в диапазоне [L, R] и, наконец, вернув длину результирующей строки.
Временная сложность : O((R-L+1) * 26)
Вспомогательное пространство : O((R-L+1) * 26)

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

  • Создайте массив префиксов ' prefix ' для хранения совокупной суммы лексикографического значения текущего символа.
  • Чтобы получить ответ заданного [L, R]: найти разность префикса [R] и префикса [L-1] , если L > 0 и префикса [L] , если L = 0, чтобы получить ответ окна ( П-Л+1 ).
  • Примечание . Этот подход эффективно работает в случае нескольких запросов.

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

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

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

  • Переберите диапазон [L, R] и добавьте к ответу соответствующие лексикографические значения.

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

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

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