Shifting Letters

Med

#0802Time: O(N^2), where N is the length of the string `s`. The outer loop runs N times, and the inner loop runs up to N times (for `i = N-1`, it runs N times). This results in a total of 1 + 2 + ... + N = N*(N+1)/2 operations, which is quadratic.Space: O(N) to store the character array for the result. In Java, strings are immutable, so creating a character array or `StringBuilder` is necessary.

Patterns

Prefix Sum

Data structures

Array String

Prompt

You are given a string s of lowercase English letters and an integer array shifts of the same length.

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.

Example 2:

Input: s = "aaa", shifts = [1,2,3]
Output: "gfd"

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase English letters.
shifts.length == s.length
0 <= shifts[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We iterate through each element of the shifts array and, for each shifts[i], we update the first i + 1 characters of the string. This involves nested loops, where the outer loop processes each shift operation and the inner loop applies that shift to the relevant prefix of the string.

Algorithm

Convert the input string s to a character array resultChars.
Loop through the shifts array from i = 0 to n-1 (where n is the length of s).
Inside this loop, start another loop from j = 0 to i.
For each character resultChars[j], apply the shift shifts[i].
The shift operation is (char_position + shift_amount) % 26.
After all loops complete, convert resultChars back to a string.

Walkthrough

The algorithm works as follows:

Convert the input string s into a mutable character array, let's call it resultChars, to allow for easy modification of individual characters.
Iterate through the shifts array with an index i from 0 to s.length() - 1.
For each i, we need to shift the first i + 1 characters. So, we start another loop with an index j from 0 to i.
Inside the inner loop, we calculate the new character for resultChars[j]. The shift amount is shifts[i]. The new character is found by:
- Getting the 0-indexed position of the character: originalPos = resultChars[j] - 'a'.
- Adding the shift amount and taking the result modulo 26 to handle wrapping around from 'z' to 'a': newPos = (originalPos + shifts[i]) % 26.
- Converting the new position back to a character: resultChars[j] = (char)('a' + newPos).
After the outer loop completes, all shifts have been applied. We convert the resultChars array back to a string and return it.

1class Solution {2    public String shiftingLetters(String s, int[] shifts) {3        char[] resultChars = s.toCharArray();4        int n = s.length();5 6        for (int i = 0; i < n; i++) {7            int shiftAmount = shifts[i];8            for (int j = 0; j <= i; j++) {9                int originalPos = resultChars[j] - 'a';10                // We need to handle large shift amounts, so we take modulo 2611                int newPos = (originalPos + shiftAmount) % 26;12                resultChars[j] = (char) ('a' + newPos);13            }14        }15 16        return new String(resultChars);17    }18}

Complexity

Time

O(N^2), where N is the length of the string `s`. The outer loop runs N times, and the inner loop runs up to N times (for `i = N-1`, it runs N times). This results in a total of 1 + 2 + ... + N = N*(N+1)/2 operations, which is quadratic.

Space

O(N) to store the character array for the result. In Java, strings are immutable, so creating a character array or `StringBuilder` is necessary.

Trade-offs

Pros

Simple to understand as it directly translates the problem statement into code.
Requires minimal algorithmic insight.

Cons

Highly inefficient due to the nested loops.
Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints (N up to 10^5).

A more efficient approach avoids re-calculating shifts for the same character multiple times. By observing the pattern of shifts, we can see that a character at index i is affected by all shifts from shifts[i] to shifts[n-1]. The total shift for s[i] is the sum of shifts[i], shifts[i+1], ..., shifts[n-1]. This is a classic suffix sum pattern. We can pre-calculate the total shift for each character in a single pass and then apply it.

Algorithm

Convert the input string s to a character array resultChars.
Initialize a long variable currentShift to 0.
Iterate from the end of the string to the beginning (i from n-1 down to 0).
Update the cumulative shift: currentShift = (currentShift + shifts[i]) % 26.
Calculate the new character for resultChars[i] by applying currentShift.
Update resultChars[i] with the new character.
After the loop, convert resultChars back to a string and return it.

Walkthrough

The core idea is to determine the final, cumulative shift for each character before modifying the string. Let totalShift[i] be the total amount character s[i] needs to be shifted.

s[n-1] is only shifted by shifts[n-1]. So, totalShift[n-1] = shifts[n-1].
s[n-2] is shifted by shifts[n-2] and shifts[n-1]. So, totalShift[n-2] = shifts[n-2] + shifts[n-1].
In general, totalShift[i] = shifts[i] + shifts[i+1] + ... + shifts[n-1]. This can be rewritten as totalShift[i] = shifts[i] + totalShift[i+1].

This relationship allows us to compute all total shifts in a single pass, iterating from right to left.

The algorithm is as follows:

Convert the input string s to a character array resultChars.
Initialize a variable currentShift to 0. This will keep track of the cumulative shift from the right. Since the sum of shifts can exceed the capacity of a 32-bit integer, we should use a long.
Iterate from the end of the string to the beginning (i.e., i from n-1 down to 0).
In each iteration, update the currentShift: currentShift = (currentShift + shifts[i]) % 26. We take the modulo at each step to keep the number manageable.
Now, currentShift holds the total shift amount for the character at index i. Apply this shift:
- originalPos = resultChars[i] - 'a'.
- newPos = (originalPos + (int)currentShift) % 26.
- resultChars[i] = (char)('a' + newPos).
After the loop, resultChars contains the final characters. Convert it back to a string.

This approach combines the calculation of suffix sums and the application of shifts into a single, efficient pass.

1class Solution {2    public String shiftingLetters(String s, int[] shifts) {3        char[] resultChars = s.toCharArray();4        int n = s.length();5        long currentShift = 0;6 7        // Iterate from right to left8        for (int i = n - 1; i >= 0; i--) {9            // Add the current shift and take modulo 26 to find the total shift for this position10            currentShift = (currentShift + shifts[i]) % 26;11            12            // Apply the total shift to the character13            int originalPos = resultChars[i] - 'a';14            int newPos = (originalPos + (int)currentShift) % 26;15            resultChars[i] = (char) ('a' + newPos);16        }17 18        return new String(resultChars);19    }20}

Complexity

Time

O(N), where N is the length of the string `s`. We iterate through the string and the shifts array only once from right to left.

Space

O(N) to store the character array for the result. This is necessary because strings are immutable in Java. The space for the `currentShift` variable is O(1).

Trade-offs

Pros

Optimal linear time complexity, making it very efficient.
Processes the input in a single pass.
Handles large inputs within the time limits.

Cons

Slightly less intuitive than the brute-force approach as it requires identifying the suffix sum pattern.

Solutions

Solution

1class Solution { public String shiftingLetters ( String s , int [] shifts ) { char [] cs = s . toCharArray (); int n = cs . length ; long t = 0 ; for ( int i = n - 1 ; i >= 0 ; -- i ) { t += shifts [ i ]; int j = ( int ) (( cs [ i ] - 'a' + t ) % 26 ); cs [ i ] = ( char ) ( 'a' + j ); } return String . valueOf ( cs ); } }

1class Solution { public: string shiftingLetters ( string s , vector < int >& shifts ) { long long t = 0 ; int n = s . size (); for ( int i = n - 1 ; ~ i ; -- i ) { t += shifts [ i ]; int j = ( s [ i ] - 'a' + t ) % 26 ; s [ i ] = 'a' + j ; } return s ; } };

1class Solution : def shiftingLetters ( self , s : str , shifts : List [ int ]) -> str : n , t = len ( s ), 0 s = list ( s ) for i in range ( n - 1 , - 1 , - 1 ): t += shifts [ i ] j = ( ord ( s [ i ]) - ord ( 'a' ) + t ) % 26 s [ i ] = ascii_lowercase [ j ] return '' . join ( s )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem