Shifting Letters

Problem Statement

In this problem, you are equipped with a string s containing lowercase English letters and a corresponding integer array shifts of the same length as s. The task involves using the array shifts to alter the string s by systematically shifting its characters based on the values found in shifts.

The function shift() is defined for shifting a letter to its subsequent one in the alphabet, with a wrap-around mechanism such that after 'z' we loop back to 'a'. Each element shifts[i] specifies how many shifts the first i + 1 letters in the string should undergo.

The goal is to apply the above operations in sequence and return the resulting string after all shifts have been executed.

Examples

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.

Example 2

Input:

s = "aaa", shifts = [1,2,3]

Output:

"gfd"

Constraints

• 1 <= s.length <= 105
• s consists of lowercase English letters.
• shifts.length == s.length
• 0 <= shifts[i] <= 109

Approach and Intuition

1. Understand character manipulation with wraps:

   • Recognize that each letter is shifted to the next one according to its ASCII value, with 'z' wrapping around to 'a'. This can be effectively handled using modulo operations with 26 (total number of English alphabets).

2. Accumulate shifts:

   • Given each shifts[i] affects every character from the start of the string to the index i, the effect of shifts needs to be accumulated. Sum up the effects of all shifts[j] for j from i to the end of the array for each character at index i.

3. Applying shifts iteratively and efficiently:

   • Initialize an array to accumulate shifts for each character position.
   • Traverse the shifts array from right to left, maintaining a running sum indicating cumulative shifts needed up to the current point. Use this sum to update the shift required for each position.
   • Modify each character of s based on the calculated shift using the ASCII and modulo operation, and directly update the string.

4. Output the modified string:

   • After adjusting all characters based on their respective and accumulated shifts, the modified string is the expected result.

By discerning the overlapping impacts of each shifts[i] via an accumulating pattern and leveraging efficient character calculations, this method ensures minimal redundancy and maximizes speed, while avoiding the pitfalls of modifying the string excessively.

Solutions

class Solution {
    public String modifyLetters(String inputStr, int[] modifications) {
        StringBuilder resultBuilder = new StringBuilder();
        int totalShift = 0;
        for (int mod : modifications)
            totalShift = (totalShift + mod) % 26;

        for (int pos = 0; pos < inputStr.length(); ++pos) {
            int charPosition = inputStr.charAt(pos) - 'a';
            resultBuilder.append((char) ((charPosition + totalShift) % 26 + 97));
            totalShift = Math.floorMod(totalShift - modifications[pos], 26);
        }

        return resultBuilder.toString();
    }
}