Formatted question description: https://leetcode.ca/all/848.html

848. Shifting Letters

Level

Medium

Description

We have a string S of lowercase letters, and an integer array shifts.

Call the shift of a letter, the next letter in the alphabet, (wrapping around so that 'z' becomes 'a'). 

For example, shift('a') = 'b', shift('t') = 'u', and shift('z') = 'a'.

Now for each shifts[i] = x, we want to shift the first i+1 letters of S, x times.

Return the final string after all such shifts to S are applied.

Example 1:

Input: S = “abc”, shifts = [3,5,9]

Output: “rpl”

Explanation:

We start with “abc”. After shifting the first 1 letters of S by 3, we have “dbc”. After shifting the first 2 letters of S by 5, we have “igc”. After shifting the first 3 letters of S by 9, we have “rpl”, the answer.

Note:

  1. 1 <= S.length = shifts.length <= 20000
  2. 0 <= shifts[i] <= 10 ^ 9

Solution

Calculate accumulative shifts for each index, from last to first. Since there are only 26 lowercase letters, the shifts should do modulo operation by 26. After accumulative shifts are calculated, do the accumulative shifts for each index.

class Solution {
    public String shiftingLetters(String S, int[] shifts) {
        int length = shifts.length;
        shifts[length - 1] %= 26;
        for (int i = length - 2; i >= 0; i--)
            shifts[i] = (shifts[i] + shifts[i + 1]) % 26;
        char[] array = S.toCharArray();
        for (int i = 0; i < length; i++) {
            int num = array[i] - 'a';
            num = (num + shifts[i]) % 26;
            array[i] = (char) (num + 'a');
        }
        return new String(array);
    }
}

All Problems

All Solutions