541. Reverse String II
Description
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 <= 104sconsists of only lowercase English letters.1 <= k <= 104
Solutions
Solution 1: Two Pointers
We can traverse the string $\textit{s}$, iterating over every $\textit{2k}$ characters, and then use the two-pointer technique to reverse the first $\textit{k}$ characters among these $\textit{2k}$ characters.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the string $\textit{s}$.
Python3
class Solution:
def reverseStr(self, s: str, k: int) -> str:
cs = list(s)
for i in range(0, len(cs), 2 * k):
cs[i : i + k] = reversed(cs[i : i + k])
return "".join(cs)
Java
class Solution {
public String reverseStr(String s, int k) {
char[] cs = s.toCharArray();
int n = cs.length;
for (int i = 0; i < n; i += k * 2) {
for (int l = i, r = Math.min(i + k - 1, n - 1); l < r; ++l, --r) {
char t = cs[l];
cs[l] = cs[r];
cs[r] = t;
}
}
return new String(cs);
}
}
C++
class Solution {
public:
string reverseStr(string s, int k) {
int n = s.size();
for (int i = 0; i < n; i += 2 * k) {
reverse(s.begin() + i, s.begin() + min(i + k, n));
}
return s;
}
};
Go
func reverseStr(s string, k int) string {
cs := []byte(s)
n := len(cs)
for i := 0; i < n; i += 2 * k {
for l, r := i, min(i+k-1, n-1); l < r; l, r = l+1, r-1 {
cs[l], cs[r] = cs[r], cs[l]
}
}
return string(cs)
}
TypeScript
function reverseStr(s: string, k: number): string {
const n = s.length;
const cs = s.split('');
for (let i = 0; i < n; i += 2 * k) {
for (let l = i, r = Math.min(i + k - 1, n - 1); l < r; l++, r--) {
[cs[l], cs[r]] = [cs[r], cs[l]];
}
}
return cs.join('');
}