Leetcode 848: Shifting Letters

Input: You are given a string `s` consisting of lowercase English letters and an integer array `shifts` of the same length. Each element of `shifts[i]` represents how many times you need to shift the first `i + 1` letters of `s`.

Example: Input: s = 'abc', shifts = [3, 5, 9]

Constraints:

• 1 <= s.length <= 10^5

• s consists of lowercase English letters.

• shifts.length == s.length

• 0 <= shifts[i] <= 10^9

Output: Return the final string after applying all the shifts to `s` as specified by the array `shifts`.

Example: Output: 'rpl'

Constraints:

• The final string is derived by applying the shifts progressively to the characters of `s`.

Goal: The goal is to compute the final string after applying all the shifts to the string `s`.

Steps:

• Step 1: Process the shifts array by calculating cumulative shifts from the end of the string towards the beginning.

• Step 2: For each character in `s`, apply the shift operation by moving the character forward in the alphabet by the corresponding number of shifts (considering the wrap-around).

• Step 3: Return the resulting string after all shifts have been applied.

Goal: Ensure that the solution handles the problem constraints efficiently, especially with large input sizes.

Steps:

• The array `shifts` and the string `s` will always have the same length.

• The shifts array will contain values between 0 and 10^9, so operations must handle large values efficiently.

Assumptions:

• The string `s` contains only lowercase English letters.

• The length of the string `s` and the array `shifts` will always match.

• Input: Input: s = 'abc', shifts = [3, 5, 9]

• Explanation: Initially, the string is 'abc'. After shifting the first 1 letter by 3, it becomes 'dbc'. Then, shifting the first 2 letters by 5 results in 'igc'. Finally, shifting the first 3 letters by 9 gives 'rpl'. Hence, the final result is 'rpl'.

• Input: Input: s = 'aaa', shifts = [1, 2, 3]

• Explanation: The string starts as 'aaa'. After shifting the first 1 letter by 1, it becomes 'b'. Then, shifting the first 2 letters by 2 gives 'd'. Finally, shifting the first 3 letters by 3 results in 'gfd'. Thus, the final result is 'gfd'.

Approach: To solve the problem efficiently, we process the shifts in reverse order and apply cumulative shifts progressively to each character in the string.

Observations:

• The shifts for each character depend on the sum of shifts from the previous positions.

• Instead of repeatedly applying shifts from the start, we can accumulate shifts from the last character and apply them once in one pass.

• By calculating cumulative shifts backwards, we avoid redundant calculations and reduce the complexity of applying shifts.

Steps:

• Step 1: Reverse process the shifts array to calculate cumulative shifts.

• Step 2: For each character in `s`, update it using the cumulative shift and apply the modulo operation for wrapping around the alphabet.

• Step 3: Return the updated string after all shifts have been applied.

Empty Inputs:

• The input string `s` will not be empty as per the problem constraints.

Large Inputs:

• Ensure the solution can handle the upper constraint where the length of `s` is 10^5 and shift values can be as large as 10^9.

Special Values:

• If the shift value is 0 for any index, the corresponding character will not be altered.

Constraints:

• The solution should be optimized to handle large shift values efficiently.

string shiftingLetters(string s, vector<int>& shifts) {

    int n = shifts.size();
    for(int i = n - 2; i >= 0; i--)
    shifts[i] = (shifts[i] + shifts[i + 1] ) % 26;

    for(int i = 0; i < s.size(); i++)
    s[i] = 'a' + ((s[i] - 'a'+ shifts[i]) % 26);

    return s;
}

1 : Function Declaration

string shiftingLetters(string s, vector<int>& shifts) {

The function `shiftingLetters` takes a string `s` and a vector `shifts` that specifies how much to shift each letter in `s`.

2 : Get Vector Size

    int n = shifts.size();

The size of the `shifts` vector is stored in `n`.

3 : Backward Cumulative Shifts

    for(int i = n - 2; i >= 0; i--)

Iterate backward through the `shifts` vector, from second-to-last element to the first.

4 : Cumulative Shift Update

    shifts[i] = (shifts[i] + shifts[i + 1] ) % 26;

Update each shift to include the shift of the next letter, making it cumulative. The modulo 26 ensures the shift stays within the bounds of the alphabet.

5 : Iterate Through String

    for(int i = 0; i < s.size(); i++)

Loop through each character in the string `s`.

6 : Apply Shift to Character

    s[i] = 'a' + ((s[i] - 'a'+ shifts[i]) % 26);

Shift each character in `s` by the corresponding value in the `shifts` vector, ensuring it wraps around the alphabet using modulo 26.

7 : Return Result

    return s;

Return the shifted string `s`.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) as we only need to process the string once and calculate the shifts in one pass.

Best Case: O(1)

Worst Case: O(n)

Description: The space complexity is O(n) due to the storage of the shifts array and the modified string `s`.

Leetcode 848: Shifting Letters

Explore →