Abstract / Summary

Given an encrypted string and a key string, return the decrypted string by repeating key letters to match the encrypted string length.

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 68% (100k+ submissions).

Typical patterns to solve this problem:

• 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 defines a class Solution with a single method getEncryptedString. This method receives a source string s and an integer offset k, and produces a new string where each character is shifted cyclically by k positions within the original string. The core of the algorithm is expressed in a compact list comprehension that builds the reordered characters, followed by a join that assembles them into the final result.

Key Steps and Corresponding Code

The method can be broken down into three logical stages:

1. Iterating Over the Input String The enumerate function supplies both the current index i and the character c from the original string. Although c is not used directly in the computation, its presence enables the enumeration to drive the iteration.

   for i, c in enumerate(s)

2. Computing the Target Position For each index i, the target position is calculated by adding the offset k and applying the modulo operator with the length of s. This ensures that the index wraps around when it exceeds the bounds of the string.

   (i + k) % len(s)

3. Collecting Characters and Forming the Result The character located at the computed target position is retrieved from s. All such characters are gathered into a list via the list comprehension, and ''.join concatenates them into the final encrypted string.

   "".join([ s[(i + k) % len(s)] for i, c in enumerate(s) ])

Edge Cases Handled by the Implementation

The algorithm gracefully manages several boundary conditions without requiring explicit checks:

• Empty Input String When s is an empty string, len(s) evaluates to zero. The list comprehension iterates over an empty sequence, producing an empty list, and ''.join returns an empty string. No division-by-zero error occurs because the loop body is never executed.

• Zero Offset (k = 0) Adding zero to each index leaves the modulo operation unchanged, so each character maps to its original position. The output is identical to the input string.

• Offset Larger Than the String Length The modulo operation reduces any large k to an effective shift within the range [0, len(s) - 1]. For example, with len(s) = 5 and k = 12, the effective shift becomes 12 % 5 = 2, yielding the same result as a shift of two positions.

• Negative Offsets Python’s modulo with a negative dividend yields a non-negative remainder, effectively converting a leftward shift into the corresponding rightward shift. Thus, k = -1 results in each character moving one position to the left, wrapping the first character to the end.

Performance Optimizations Observed

The implementation leverages several idiomatic Python techniques that contribute to efficient execution:

• List Comprehension Over Explicit Loops The use of a list comprehension creates the list of characters in a single, tightly-controlled construct. This avoids the overhead of repeatedly invoking append on a mutable list or concatenating strings inside a loop, both of which can degrade performance due to repeated memory allocations.

• Single Pass Construction The algorithm processes each character exactly once, performing a constant amount of work per iteration (index arithmetic and a single character lookup). This linear traversal ensures that the runtime scales proportionally with the length of the input string.

• String Joining By deferring the concatenation of characters until after the list is fully built, the code benefits from the highly optimized implementation of str.join. This method pre-computes the total size of the resulting string and allocates memory only once, eliminating the repeated copying that would occur with incremental concatenation.

• Modulo Operation for Index Wrapping The modulo operator provides a concise and fast way to wrap indices without conditional branches. This eliminates the need for explicit if statements to handle wrap-around cases, reducing branch misprediction overhead in tight loops.

Overall, the method combines clear, expressive Python constructs with low-overhead operations to deliver an implementation that is both readable and performant for typical string sizes.

Imagine a row of colorful building blocks lined up in a long train. Each block has a letter painted on it. The code is like a little robot helper designed to create a secret code using these letters.

The robot starts at the first block and peeks ahead by counting a specific number of spots forward. If the robot reaches the end of the train, it simply loops back around to the very beginning, like a race track that never ends. It grabs the letter sitting at that new spot and writes it down on a fresh piece of paper.

The robot repeats this process for every single block in the train, one by one. Once it has visited every block and picked a new letter for each spot, it glues all those new letters together to form a brand new secret message.

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		Python		Java	C++		TS
	WalkCCC		Python		Java	C++
	leetcode.ca		Python		Java	C++	Go	TS
	Progiez		Python		Java	C++
github	charles-wangkai				Java
	everthis			JS
	fartem	Ruby
	fsq		Python
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
fartem	Ruby
fsq	Python

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