# 541. Reverse String II
LeetCode Problem Link (opens new window)
Given a string s and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string.
If there are less 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 keep the rest as is.
Example:
Input: s = "abcdefg", k = 2
Output: "bacdfeg"
# Thought Process
This problem boils down to simulating the rule specified in the problem.
Some people might write a lot of code or use an additional counter for handling the logic of reversing every first k characters in the interval of 2k characters.
However, during the traversal, you only need to increment i by 2 * k each time. The focus here should be on calculating the starting point for each 2 * k interval.
Since we need to find the starting point of each 2 * k interval, writing it like this will make the program much more efficient.
When you need to handle a string in chunks according to a fixed pattern, consider modifying the for loop expression to make things easier.
Performance is as follows:
Now, should we use a library function for the reversing part? It doesn't really matter since it's not the key part of solving the problem. Using reverse to handle the reversal is perfectly fine.
The version using C++ reverse library function is as follows:
class Solution {
public:
string reverseStr(string s, int k) {
for (int i = 0; i < s.size(); i += (2 * k)) {
if (i + k <= s.size()) {
reverse(s.begin() + i, s.begin() + i + k);
} else {
reverse(s.begin() + i, s.end());
}
}
return s;
}
};
2
3
4
5
6
7
8
9
10
11
12
13
- Time Complexity: O(n)
- Space Complexity: O(1)
We can also implement our own reverse function, which is similar to the problem 344.Reverse String (opens new window).
Below is an implementation of the reverse function where the range is inclusive on both ends:
class Solution {
public:
void reverse(string& s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
swap(s[i], s[j]);
}
}
string reverseStr(string s, int k) {
for (int i = 0; i < s.size(); i += (2 * k)) {
if (i + k <= s.size()) {
reverse(s, i, i + k - 1);
continue;
}
reverse(s, i, s.size() - 1);
}
return s;
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
- Time Complexity: O(n)
- Space Complexity: depends on whether the language treats strings as mutable.
Another approach:
class Solution {
public:
string reverseStr(string s, int k) {
int n = s.size(), pos = 0;
while(pos < n){
if(pos + k < n) reverse(s.begin() + pos, s.begin() + pos + k);
else reverse(s.begin() + pos, s.end());
pos += 2 * k;
}
return s;
}
};
2
3
4
5
6
7
8
9
10
11
12
- Time Complexity: O(n)
- Space Complexity: O(1)
# Other Language Versions
# C：
char * reverseStr(char * s, int k){
int len = strlen(s);
for (int i = 0; i < len; i += (2 * k)) {
k = i + k > len ? len - i : k;
int left = i;
int right = i + k - 1;
while (left < right) {
char temp = s[left];
s[left++] = s[right];
s[right--] = temp;
}
}
return s;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Java：
// Solution 1
class Solution {
public String reverseStr(String s, int k) {
StringBuffer res = new StringBuffer();
int length = s.length();
int start = 0;
while (start < length) {
StringBuffer temp = new StringBuffer();
int firstK = (start + k > length) ? length : start + k;
int secondK = (start + (2 * k) > length) ? length : start + (2 * k);
temp.append(s.substring(start, firstK));
res.append(temp.reverse());
if (firstK < secondK) {
res.append(s.substring(firstK, secondK));
}
start += (2 * k);
}
return res.toString();
}
}
// Solution 2
class Solution {
public String reverseStr(String s, int k) {
char[] ch = s.toCharArray();
for(int i = 0; i < ch.length; i += 2 * k){
int start = i;
int end = Math.min(ch.length - 1, start + k - 1);
while(start < end){
ch[start] ^= ch[end];
ch[end] ^= ch[start];
ch[start] ^= ch[end];
start++;
end--;
}
}
return new String(ch);
}
}
// Solution 2 with temp variable
class Solution {
public String reverseStr(String s, int k) {
char[] ch = s.toCharArray();
for(int i = 0;i < ch.length;i += 2 * k){
int start = i;
int end = Math.min(ch.length - 1,start + k - 1);
while(start < end){
char temp = ch[start];
ch[start] = ch[end];
ch[end] = temp;
start++;
end--;
}
}
return new String(ch);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// Solution 3
class Solution {
public String reverseStr(String s, int k) {
char[] ch = s.toCharArray();
for (int i = 0; i< ch.length; i += 2 * k) {
if (i + k <= ch.length) {
reverse(ch, i, i + k -1);
continue;
}
reverse(ch, i, ch.length - 1);
}
return new String(ch);
}
public void reverse(char[] ch, int i, int j) {
for (; i < j; i++, j--) {
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Python：
class Solution:
def reverseStr(self, s: str, k: int) -> str:
def reverse_substring(text):
left, right = 0, len(text) - 1
while left < right:
text[left], text[right] = text[right], text[left]
left += 1
right -= 1
return text
res = list(s)
for cur in range(0, len(s), 2 * k):
res[cur: cur + k] = reverse_substring(res[cur: cur + k])
return ''.join(res)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Python3 (v2):
class Solution:
def reverseStr(self, s: str, k: int) -> str:
p = 0
while p < len(s):
p2 = p + k
s = s[:p] + s[p: p2][::-1] + s[p2:]
p = p + 2 * k
return s
2
3
4
5
6
7
8
# Python3 (v3):
class Solution:
def reverseStr(self, s: str, k: int) -> str:
i = 0
chars = list(s)
while i < len(chars):
chars[i:i + k] = chars[i:i + k][::-1]
i += k * 2
return ''.join(chars)
2
3
4
5
6
7
8
9
10
# Go：
func reverseStr(s string, k int) string {
ss := []byte(s)
length := len(s)
for i := 0; i < length; i += 2 * k {
if i + k <= length {
reverse(ss[i:i+k])
} else {
reverse(ss[i:length])
}
}
return string(ss)
}
func reverse(b []byte) {
left := 0
right := len(b) - 1
for left < right {
b[left], b[right] = b[right], b[left]
left++
right--
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# JavaScript:
/**
* @param {string} s
* @param {number} k
* @return {string}
*/
var reverseStr = function(s, k) {
const len = s.length;
let resArr = s.split("");
for(let i = 0; i < len; i += 2 * k) {
let l = i - 1, r = i + k > len ? len : i + k;
while(++l < --r) [resArr[l], resArr[r]] = [resArr[r], resArr[l]];
}
return resArr.join("");
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# TypeScript：
function reverseStr(s: string, k: number): string {
let left: number, right: number;
let arr: string[] = s.split('');
let temp: string;
for (let i = 0, length = arr.length; i < length; i += 2 * k) {
left = i;
right = (i + k - 1) >= length ? length - 1 : i + k - 1;
while (left < right) {
temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
return arr.join('');
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Swift:
func reverseStr(_ s: String, _ k: Int) -> String {
var ch = Array(s)
for i in stride(from: 0, to: ch.count, by: 2 * k) {
var left = i
var right = min(s.count - 1, left + k - 1)
while left < right {
(ch[left], ch[right]) = (ch[right], ch[left])
left += 1
right -= 1
}
}
return String(ch)
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# C#：
public class Solution
{
public string ReverseStr(string s, int k)
{
Span<char> span = s.ToCharArray().AsSpan();
for (int i = 0; i < span.Length; i += 2 * k)
{
span[i + k < span.Length ? i..(i + k) : i..].Reverse();
}
return span.ToString();
}
}
2
3
4
5
6
7
8
9
10
11
12
# Scala:
Version 1: (straightforward solution)
object Solution {
def reverseStr(s: String, k: Int): String = {
val res = s.toCharArray
for (i <- s.indices by 2 * k) {
if (i + k > res.length) {
reverse(res, i, s.length - 1)
} else {
reverse(res, i, i + k - 1)
}
}
new String(res)
}
def reverse(s: Array[Char], start: Int, end: Int): Unit = {
var (left, right) = (start, end)
while (left < right) {
var tmp = s(left)
s(left) = s(right)
s(right) = tmp
left += 1
right -= 1
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Version 2: Use grouped to separate every k characters and use zipWithIndex to add an index to each array, then use map to transform; if index%2==0 reverse it, otherwise keep it as is, and finally convert it back to String
object Solution {
def reverseStr(s: String, k: Int): String = {
s.grouped(k)
.zipWithIndex
.map {
case (subStr, index) =>
if (index % 2 == 0) subStr.reverse else subStr
}
.mkString
}
}
2
3
4
5
6
7
8
9
10
11
Version 3: (recursive solution)
import scala.annotation.tailrec
object Solution {
def reverseStr(s: String, k: Int): String = {
@tailrec
def reverse(s: String, needToReverse: Boolean, history: String): String = {
val subStr = if (needToReverse) s.take(k).reverse else s.take(k)
if (s.length < k) history + subStr
else reverse(s.drop(k), !needToReverse, history + subStr)
}
reverse(s, true, "")
}
}
2
3
4
5
6
7
8
9
10
11
12
13
# Rust:
impl Solution {
pub fn reverse(s: &mut Vec<char>, mut begin: usize, mut end: usize){
while begin < end {
let temp = s[begin];
s[begin] = s[end];
s[end] = temp;
begin += 1;
end -= 1;
}
}
pub fn reverse_str(s: String, k: i32) -> String {
let len = s.len();
let k = k as usize;
let mut s = s.chars().collect::<Vec<_>>();
for i in (0..len).step_by(2 * k) {
if i + k < len {
Self::reverse(&mut s, i, i + k - 1);
}
else {
Self::reverse(&mut s, i, len - 1);
}
}
s.iter().collect::<String>()
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25