# Reverse String II
**Difficulty:** EASY
[External](https://leetcode.com/problems/reverse-string-ii)
Canonical: https://scaleengineer.com/dsa/problems/reverse-string-ii
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String
---
## Problem
Given a string `s` and an integer `k`, reverse the first `k` characters for every `2k` characters counting from the start of the string.

If there are fewer than `k` characters left, reverse all of them. If there are less than `2k` but greater than or equal to `k` characters, then reverse the first `k` characters and leave the other as original.

**Example 1:**

**Input:** s = "abcdefg", k = 2
**Output:** "bacdfeg"

**Example 2:**

**Input:** s = "abcd", k = 2
**Output:** "bacd"

**Constraints:**

* `1 <= s.length <= 104`
* `s` consists of only lowercase English letters.
* `1 <= k <= 104`

# Approaches
## Simulation with StringBuilder
This approach directly simulates the process described in the problem. We iterate through the string, building a new reversed string piece by piece using a `StringBuilder`. For every `2k` characters, we take the first `k`, reverse them, and append them to our result, followed by the next `k` characters which are appended without modification.
**Time:** O(N), where N is the length of the string. We iterate through the string once. Operations inside the loop like `substring`, `StringBuilder` creation, and `reverse` take time proportional to `k`. The total time is the sum over all blocks, which is linear in N. · **Space:** O(N). A `StringBuilder` of size N is used to build the result. Additionally, temporary substrings and `StringBuilder` objects of size up to `k` are created in each iteration, contributing to the overall space usage.
**Pros:** Conceptually straightforward, directly translating the problem statement into code.; Relatively easy to implement without complex data structures.
**Cons:** Less efficient due to the creation of multiple temporary string and `StringBuilder` objects within the loop. This can lead to higher memory overhead and performance degradation from frequent garbage collection.
### Explanation
We initialize a `StringBuilder` to construct the final string. The logic iterates through the input string `s` with a step size of `2k`. In each step, we handle a block of up to `2k` characters.

1.  **Identify and Reverse**: We first determine the segment to be reversed. This segment starts at the current index `i` and ends at `min(i + k, s.length())`. This `min` function correctly handles the case where fewer than `k` characters are left. We extract this substring, reverse it using a temporary `StringBuilder`, and append it to our main result `StringBuilder`.
2.  **Append Unchanged Part**: Next, we identify the second part of the block, which should not be reversed. This segment starts where the first one ended and goes up to `min(i + 2k, s.length())`. We extract this substring and append it directly to the result.
3.  **Iteration**: We then advance our main index `i` by `2k` to move to the next block.

After the loop has processed the entire string, we convert the `StringBuilder` to a string and return it.

```java
class Solution {
    public String reverseStr(String s, int k) {
        StringBuilder result = new StringBuilder();
        int i = 0;
        int n = s.length();
        while (i < n) {
            int reverseEnd = Math.min(i + k, n);
            StringBuilder reversedPart = new StringBuilder(s.substring(i, reverseEnd));
            result.append(reversedPart.reverse());

            if (reverseEnd < n) {
                int nonReverseEnd = Math.min(i + 2 * k, n);
                result.append(s.substring(reverseEnd, nonReverseEnd));
            }
            
            i += 2 * k;
        }
        return result.toString();
    }
}
```
### Algorithm
*   Initialize an empty `StringBuilder` called `result`.
*   Initialize an index `i = 0`.
*   Loop while `i` is less than the length of the string `s`:
    *   Calculate the end index `j` of the part to be reversed: `j = min(i + k, s.length())`.
    *   Extract the substring from `i` to `j`.
    *   Reverse this substring and append it to `result`.
    *   Calculate the end index `l` of the current `2k` block: `l = min(i + 2k, s.length())`.
    *   If `j < l`, append the substring from `j` to `l` to `result`.
    *   Increment `i` by `2k`.
*   Return `result.toString()`.

## In-place Reversal with Character Array
A more optimized approach involves converting the string to a character array to perform the reversals in-place. This avoids the overhead of creating new string objects repeatedly. We iterate through the array in steps of `2k` and reverse the required segments directly within the array using a two-pointer technique.
**Time:** O(N), where N is the length of the string. We traverse the array once. Each character is visited a constant number of times (once in the main loop, and at most once during a reversal swap). This results in a linear time complexity. · **Space:** O(N). In Java, this approach requires `O(N)` space to store the character array, as strings are immutable. In languages with mutable strings, this could be an `O(1)` space solution (excluding input storage).
**Pros:** More efficient in terms of both time and memory as it avoids creating numerous temporary objects.; Modifies data in-place (on the character array), which is an efficient and common programming pattern.
**Cons:** Requires an initial `O(N)` space overhead to convert the immutable string to a mutable character array in Java.
### Explanation
Since strings are immutable in Java, we first convert the input string `s` into a character array `a`. This allows us to modify characters directly.

The main logic iterates through this array with a `start` index, which is incremented by `2k` in each step. This `start` index marks the beginning of each block to be processed.

For each block, we need to reverse the first `k` characters. The indices for this reversal are from `start` to `min(start + k - 1, a.length - 1)`. The `min` function is key to correctly handling the final part of the string, which might be shorter than `k` or `2k`.

A helper function, `reverse(char[] a, int left, int right)`, performs the in-place reversal. It uses two pointers, `left` and `right`, initialized to the start and end of the segment. It swaps the characters at these pointers and moves them towards each other until they cross.

After the loop finishes, the character array `a` contains the desired arrangement. We then construct a new string from this array and return it.

```java
class Solution {
    public String reverseStr(String s, int k) {
        char[] a = s.toCharArray();
        for (int start = 0; start < a.length; start += 2 * k) {
            int i = start;
            int j = Math.min(start + k - 1, a.length - 1);
            reverse(a, i, j);
        }
        return new String(a);
    }

    private void reverse(char[] a, int i, int j) {
        while (i < j) {
            char temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
            j--;
        }
    }
}
```
### Algorithm
*   Convert the input string `s` to a character array `a`.
*   Iterate through the array with an index `start` from `0` to `a.length - 1`, with a step of `2 * k`.
*   In each iteration, determine the `left` and `right` boundaries of the segment to reverse:
    *   `left = start`
    *   `right = min(start + k - 1, a.length - 1)`
*   Call a helper function `reverse(a, left, right)`.
*   The `reverse` function swaps elements from the ends towards the center using two pointers until they meet.
*   After the loop, create a new string from the modified character array `a` and return it.

# Solutions
### Java

```java
class Solution {
public
  String reverseStr(String s, int k) {
    char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i += (k << 1)) {
      for (int st = i, ed = Math.min(chars.length - 1, i + k - 1); st < ed;
           ++st, --ed) {
        char t = chars[st];
        chars[st] = chars[ed];
        chars[ed] = t;
      }
    }
    return new String(chars);
  }
}

```

### CPP

```cpp
class Solution {
public:
  string reverseStr(string s, int k) {
    for (int i = 0, n = s.size(); i < n; i += (k << 1)) {
      reverse(s.begin() + i, s.begin() + min(i + k, n));
    }
    return s;
  }
};

```

### Python

```python
''' class range(start, stop, step=1) >>> k = 1 >>> for i in range(0, 9, k): ... print(i) ... 0 1 2 3 4 5 6 7 8 >>> for i in range(0, 9, k << 1): ... print(i) ... 0 2 4 6 8 ''' ''' reversed(t[i : i + k]) VS t[i : i + k][::-1] reversed(t[i : i + k]) returns an iterator that yields elements of the sequence in reverse order more suitable when you don't need a list or are performing operations that can take advantage of an iterator like join() t[i : i + k][::-1] slicing to create a new list that is a reversed version of the slice t[i : i + k] more convenient where you need the reversed sublist to be a list >>> t = [11,22,33,44,55] >>> >>> >>> t[1:3][::-1] [33, 22] >>> >>> reversed(t[1:3]) <list_reverseiterator object at 0x109022950> >>> >>> list(reversed(t[1:3])) [33, 22] ''' class Solution : def reverseStr ( self , s : str , k : int ) -> str : t = list ( s ) for i in range ( 0 , len ( t ), k << 1 ): # protected from out-of-index error t [ i : i + k ] = reversed ( t [ i : i + k ]) return '' . join ( t ) ############ class Solution ( object ): def reverseStr ( self , s , k ): """ :type s: str :type k: int :rtype: str """ cnt = 0 isFirst = True a = "" b = "" ans = [] for c in s : if isFirst : a = c + a else : b += c cnt += 1 if cnt == k : if isFirst : ans . append ( a ) a = "" else : ans . append ( b ) b = "" isFirst = not isFirst cnt = 0 return "" . join ( ans ) + a + b
```