Abstract / Summary

Given a string and shifts for each letter, return the final string after applying the shifts and wrapping letters in the alphabet.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 54% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Prefix Sum
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the “shifting letters” problem by converting a series of range-based shift operations into a single pass over the input string. It builds a difference array to capture the net effect of all shifts, then walks through the characters while maintaining a running total of the accumulated shift. Each character is transformed using simple arithmetic on its ASCII code, producing the final shifted string.

Core Steps

Initialisation

result = ""

size  = len(s)
delta = [ 0 ] * (size + 1) # last index isn't used

A result string is prepared, the length of the input is stored, and a difference array delta of length size + 1 is allocated. The extra slot simplifies the subtraction step for the end of each interval.

Encoding Shift Directions

for start, end, direction in shifts:
    d = 2 * direction - 1 # 0 => -1, 1 => +1
    delta[start]   += d
    delta[end + 1] -= d

Each triple [start, end, direction] is processed. The expression 2 * direction - 1 maps the binary direction (0 for left, 1 for right) to the signed increment d (-1 or +1). The difference array receives +d at the interval’s start and -d just after its end, thereby recording the net contribution of that interval without iterating over every character inside it.

Accumulating Shifts and Transforming Characters

a = ord("a")
have = 0 # accumulated delta
for c, d in zip(s, delta):
    have   += d
    ascii   = ord(c) - a
    ascii  += have
    ascii  %= 26
    result += chr(ascii + a)

A base ASCII value for 'a' is stored. The variable have holds the running sum of all pending shifts as the loop progresses. For each character c and its corresponding delta entry d, have is updated, the character’s zero-based alphabet index is computed, the accumulated shift is added, and the result is wrapped into the range [0, 25] with a modulo operation. Finally, the shifted character is appended to result.

Edge Cases Handled

When the input string is empty, size becomes zero, the delta array is created with a single unused element, and the final loop iterates over an empty zip, leaving result as an empty string-exactly the expected output.

If a shift interval specifies the full length of the string (start = 0, end = size-1), the subtraction delta[end + 1] writes to the extra slot at index size, which is deliberately allocated and never read during the accumulation phase, preventing out-of-bounds errors.

The conversion of direction to d guarantees that only the two valid directions (0 or 1) produce meaningful signed increments; any other integer would still yield a deterministic signed value, but the problem constraints restrict direction to the binary set, so the code safely assumes this mapping.

Overlapping intervals are naturally merged by the additive nature of the difference array: each interval contributes its signed increment at its start and end, and the running total have automatically reflects the combined effect of all overlapping ranges.

Negative net shifts are correctly wrapped because the modulo operation on a possibly negative ascii value yields a non-negative remainder in the range [0, 25], ensuring that leftward shifts (direction 0) produce valid letters.

Performance Optimisations

The algorithm replaces a naïve double loop-where each shift would be applied to every character in its range-with a difference-array technique that records each interval’s impact in constant time. Consequently, the total work for processing all shift specifications scales linearly with the number of intervals, not with the product of intervals and string length.

The subsequent single pass over the string simultaneously accumulates the net shift and performs the character transformation, eliminating the need for a secondary pass or auxiliary data structures.

Arithmetic on integer ASCII codes avoids the overhead of repeated string slicing or concatenation of intermediate results; only a single character is appended to result per iteration, and the use of chr and ord provides direct, low-level conversion.

By pre-computing the base ASCII value for 'a' once, the code avoids repeated calls to ord("a") inside the loop, shaving off unnecessary function calls.

Overall, the combination of a difference array, a running accumulator, and minimal per-character work yields an efficient solution that processes the input in linear time with a modest amount of auxiliary memory.

Imagine a long row of alphabet blocks lined up on the floor. Each block has a letter on it. You have a bucket of letters and a secret rule book for shifting them around. Sometimes you want to slide the letters one spot forward in the alphabet, and sometimes you want to slide them one spot backward.

The code starts by creating a long list of zeros. Think of these as empty markers placed underneath each letter. When the instructions in the shifts list arrive, they say to pick a range of letters and add or subtract from these markers. Instead of moving every single letter one by one immediately, the computer just scribbles down notes on where the shifts should happen in the marker list.

After all the notes are in place, the computer walks along the row of letters one more time. It keeps a running total of the shifts as it goes. If the current letter has a plus one marker, it turns an a into a b. If the marker is a minus one, it turns a b back into an a. If a letter gets shifted past z, it simply circles back to the beginning of the alphabet just like a wrapping paper roll. By the time every letter has been visited and adjusted according to the running total, a brand new string of letters is formed and placed into the result pile.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Python	Java			TS
	WalkCCC	C++		Python	Java
	leetcode.ca	C++		Python	Java		Go	TS
	Progiez	C++		Python	Java
github	charles-wangkai				Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007			Python
	Shamik07					Dart
	wisdompeak	C++
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
Shamik07	Dart
wisdompeak	C++
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality