Reverse String II
Easy · Two Pointers · Explanation and code example
Reverse the First Half of Each 2k Block
How it works
Divide the character positions into blocks of size 2k. Reverse the first k positions in each block, or all remaining characters when fewer than k remain. Leave the second half unchanged and use iteration to avoid recursion-depth limits.
Steps
- Visit block starts 0, 2k, 4k, ...
- Reverse from the block start to min(start + k - 1, last index).
- Join or return the resulting string.
Complexity
- Time: O(n).
- Space: Python O(n) for the mutable character list; C++ uses the by-value string buffer.
Things to watch for
- The last partial block still needs reversal.
- When fewer than k remain, reverse all of them.
- k is positive.
Python code example
class Solution:
def reverseStr(self, s: str, k: int) -> str:
chars = list(s)
for start in range(0, len(chars), 2 * k):
left, right = start, min(start + k - 1, len(chars) - 1)
while left < right:
chars[left], chars[right] = chars[right], chars[left]
left += 1
right -= 1
return "".join(chars)
C++ code example
class Solution {
public:
string reverseStr(string s, int k) {
for (size_t i = 0; i < s.length(); i += 2 * k) {
int l = i;
int r = min(i + k - 1, s.length() - 1);
while (l < r)
swap(s[l++], s[r--]);
}
return s;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.