LeetCode 541: Reverse String II

Problem Restatement

We are given a string s and an integer k.

Starting from the beginning of the string, for every block of 2k characters, reverse the first k characters and leave the next k characters unchanged.

There are two end cases:

The official rule is to reverse the first k characters for every 2k characters counted from the start of the string. If fewer than k characters remain, reverse all of them. If at least k but fewer than 2k remain, reverse only the first k.

Input and Output

Function shape:

def reverseStr(s: str, k: int) -> str:
    ...

Examples

Consider:

s = "abcdefg"
k = 2

Split the string into blocks of size 2k = 4.

The first block is:

"abcd"

Reverse the first 2 characters:

"ab" -> "ba"

Leave the next 2 characters unchanged:

"cd"

So the first block becomes:

"bacd"

The remaining part is:

"efg"

There are at least k characters but fewer than 2k, so reverse the first 2:

"ef" -> "fe"

and leave "g" unchanged.

The final answer is:

"bacdfeg"

Another example:

s = "abcd"
k = 2

The string has exactly 2k characters.

Reverse the first 2:

"ab" -> "ba"

Leave the next 2 unchanged:

"cd"

The answer is:

"bacd"

First Thought: Build the Result Block by Block

A direct approach is to process the string in chunks of length 2k.

For each chunk:

1. Reverse the first k characters.
2. Append the rest unchanged.

This is simple and correct.

But in Python, strings are immutable, so repeated string concatenation can create unnecessary copies.

A cleaner approach is to convert the string to a list of characters, reverse parts in place, and join at the end.

Key Insight

The positions where reversal begins are:

0, 2k, 4k, 6k, ...

So we can loop with step size:

2 * k

At each such position start, reverse the range:

[start, start + k - 1]

If fewer than k characters remain, the right boundary should stop at the end of the string.

That boundary is:

min(start + k - 1, len(s) - 1)

Algorithm

1. Convert s to a list of characters.
2. For every start in range(0, len(chars), 2 * k):
   1. Set left = start.
   2. Set right = min(start + k - 1, len(chars) - 1).
   3. Reverse characters between left and right using two pointers.
3. Join the list back into a string.
4. Return the result.

Correctness

The loop visits exactly the first index of every 2k block:

0, 2k, 4k, ...

For each block, the algorithm reverses the substring starting at that block’s first character and ending at either k characters later or the end of the string, whichever comes first.

If the block has at least k characters, this reverses exactly the first k characters.

If the block has fewer than k characters, the right boundary becomes the last character of the string, so the algorithm reverses all remaining characters.

The algorithm does not modify the second k characters of any full 2k block, because the loop jumps directly to the next block after 2k positions.

Therefore, every block is transformed exactly according to the problem rule, and the final string is correct.

Complexity

Let n = len(s).

Implementation

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        chars = list(s)
        n = len(chars)

        for start in range(0, n, 2 * k):
            left = start
            right = min(start + k - 1, n - 1)

            while left < right:
                chars[left], chars[right] = chars[right], chars[left]
                left += 1
                right -= 1

        return "".join(chars)

Code Explanation

We convert the string into a mutable list:

chars = list(s)

Then we process every 2k block:

for start in range(0, n, 2 * k):

The start index is where the next reversal begins.

The reversal range is:

left = start
right = min(start + k - 1, n - 1)

The min handles the case where fewer than k characters remain.

The two-pointer loop swaps characters until the selected segment is reversed:

while left < right:
    chars[left], chars[right] = chars[right], chars[left]
    left += 1
    right -= 1

Finally, we rebuild the string:

return "".join(chars)

Slice-Based Python Version

Python slicing can make the implementation shorter.

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        chars = list(s)

        for start in range(0, len(chars), 2 * k):
            chars[start:start + k] = reversed(chars[start:start + k])

        return "".join(chars)

This works because Python slicing safely stops at the end of the list if start + k is beyond the string length.

Testing

def run_tests():
    s = Solution()

    assert s.reverseStr("abcdefg", 2) == "bacdfeg"
    assert s.reverseStr("abcd", 2) == "bacd"
    assert s.reverseStr("abc", 4) == "cba"
    assert s.reverseStr("abcdef", 3) == "cbadef"
    assert s.reverseStr("a", 1) == "a"

    print("all tests passed")

run_tests()