Длина строки, образованной повторением каждого символа в диапазоне [L, R] данной строки, умноженной на его лексикографическое значение.
Дана строка 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 13Input: 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)