Найдите окончательную строку, увеличив префиксы заданной длины

Имея строку S и массив roll[] , где roll[i] представляет увеличение первых символов roll[i] в строке, задача состоит в том, чтобы увеличить все префиксы, упомянутые в массиве, и найти окончательную строку.

Примечание. Увеличение означает увеличение значения ASCII символа, например, увеличение «z» приведет к «a», увеличение «b» приведет к «c» и т. д.

Примеры :

Input: S = “bca”, roll[] = {1, 2, 3} 
Output: eeb
Explanation: arr[0] = 1 means roll first character of string -> cca
arr[1] = 2 means roll first two characters of string -> dda
arr[2] = 3 means roll first three characters of string -> eeb
So final ans is “eeb”.

Input: S = “zcza”, roll[] = {1, 1, 3, 4}
Output: debb

Подход : выполните шаги, чтобы решить эту проблему:

• Инициализируйте массив arr[] размера N + 1 и установите его равным 0.
• Перейдите массив a[] и увеличьте arr[0] на 1 и уменьшите arr[roll[i]] на 1. {поскольку мы используем индексацию, основанную на 0, поэтому мы делаем arr[roll[i]] -= 1 и не приб[ролл[i] + 1] -= 1}
• Запустите цикл от 1 до N и создайте массив префиксов, выполнив следующие действия: arr[i] += arr[i – 1] .
• Пройдите по массиву arr[] и вычислите arr[i] в диапазоне от 0 до 25, взяв его мод на 26 и проверьте:
  • Если arr[i] + S[i] > 'z', то измените S[i] = (S[i] + arr[i] – 26) .
  • В противном случае измените S[i] = S[i]+arr[i]
• После обхода массива arr[] верните S .

Ниже приведена реализация описанного выше подхода.

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

Статьи по Теме:

• Введение в строки — учебные пособия по структуре данных и алгоритмам
• Массив сумм префиксов — реализация и приложения в соревновательном программировании