# 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:

| Remaining Characters | Rule |
|---|---|
| Fewer than `k` | Reverse all remaining characters |
| At least `k` but fewer than `2k` | Reverse the first `k`, leave the rest unchanged |

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

| Item | Meaning |
|---|---|
| Input | A string `s` and an integer `k` |
| Output | The transformed string |
| Operation | Reverse first `k` characters in every `2k` block |
| End behavior | Reverse all if fewer than `k` remain |

Function shape:

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

## Examples

Consider:

```python
s = "abcdefg"
k = 2
```

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

The first block is:

```python
"abcd"
```

Reverse the first `2` characters:

```python
"ab" -> "ba"
```

Leave the next `2` characters unchanged:

```python
"cd"
```

So the first block becomes:

```python
"bacd"
```

The remaining part is:

```python
"efg"
```

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

```python
"ef" -> "fe"
```

and leave `"g"` unchanged.

The final answer is:

```python
"bacdfeg"
```

Another example:

```python
s = "abcd"
k = 2
```

The string has exactly `2k` characters.

Reverse the first `2`:

```python
"ab" -> "ba"
```

Leave the next `2` unchanged:

```python
"cd"
```

The answer is:

```python
"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:

```python
0, 2k, 4k, 6k, ...
```

So we can loop with step size:

```python
2 * k
```

At each such position `start`, reverse the range:

```python
[start, start + k - 1]
```

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

That boundary is:

```python
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:

```python
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)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each character is reversed at most once |
| Space | `O(n)` | Python strings are immutable, so we use a character list |

## Implementation

```python
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:

```python
chars = list(s)
```

Then we process every `2k` block:

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

The start index is where the next reversal begins.

The reversal range is:

```python
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:

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

Finally, we rebuild the string:

```python
return "".join(chars)
```

## Slice-Based Python Version

Python slicing can make the implementation shorter.

```python
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

```python
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()
```

| Test | Why |
|---|---|
| `"abcdefg", k = 2` | Standard partial final block |
| `"abcd", k = 2` | Exactly one full `2k` block |
| `"abc", k = 4` | Fewer than `k` characters remain |
| `"abcdef", k = 3` | Exactly `2k` characters |
| `"a", k = 1` | Minimum string size |