541. 反转字符串 II
题目描述
输入字符串 s 和正整数 k。从开头起，把 s 依次切成长度为 2k 的若干段，最后一段可能不足 2k。
对每一段，只把其中前 k 个字符的顺序颠倒，后面的字符保持不动。若最后一段长度不到 k，就把这一段全部颠倒；若长度在 k 与 2k 之间，仍只颠倒前 k 个。
返回处理后的字符串。
示例 1
输入：s = "abcdefg", k = 2 输出："bacdfeg"
解释：第一段 "abcd" 变为 "bacd"，剩下的 "efg" 不足 2k，只颠倒前 2 个得到 "feg"。
示例 2
输入：s = "abcd", k = 2 输出："bacd"
解释：只有一段 "abcd"，颠倒前 2 个字符得到 "bacd"。
数据范围
1 <= s.length <= 10^4s只包含小写英文字母。1 <= k <= 10^4
解题思路
让 start 以 2k 为步长遍历 0, 2k, 4k, …，每个 start 都是一段的开头。要反转的区间是 [start, min(start + k, n) - 1]：取 min 正好把两种尾部情况统一起来——剩余不足 k 个时反转到末尾，否则只反转 k 个。每个区间内用左右双指针交换，和普通的反转字符串完全一样。
为什么正确
处理到某一段时，前面各段都已是最终结果；段内 t[start..i) 和 t(j..end] 已就位，且 i + j 始终等于区间两端之和。
复杂度分析
时间 O(n)，每个字符最多被交换一次；额外空间 O(n)，用于字符列表。
易错点
右端要取 min(start + k, n) - 1，直接用 start + k - 1 在最后一段可能越界；步长是 2k 而不是 k，否则会把不该反转的后 k 个字符也反转了。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def reverseStr(self, s: str, k: int) -> str:
t = list(s)
for start in range(0, len(t), 2 * k):
i = start
j = min(start + k, len(t)) - 1
while i < j:
t[i], t[j] = t[j], t[i]
i += 1
j -= 1
return ''.join(t)class Solution {
public String reverseStr(String s, int k) {
char[] t = s.toCharArray();
for (int start = 0; start < t.length; start += 2 * k) {
int i = start;
int j = Math.min(start + k, t.length) - 1;
while (i < j) {
char c = t[i]; t[i] = t[j]; t[j] = c;
i++;
j--;
}
}
return new String(t);
}
}class Solution {
public:
string reverseStr(string s, int k) {
string t = s;
int n = t.size();
for (int start = 0; start < n; start += 2 * k) {
int i = start;
int j = min(start + k, n) - 1;
while (i < j) {
swap(t[i], t[j]);
i++;
j--;
}
}
return t;
}
};func reverseStr(s string, k int) string {
t := []byte(s)
for start := 0; start < len(t); start += 2 * k {
i := start
j := start + k
if j > len(t) {
j = len(t)
}
j--
for i < j {
t[i], t[j] = t[j], t[i]
i++
j--
}
}
return string(t)
}var reverseStr = function(s, k) {
const t = s.split('');
for (let start = 0; start < t.length; start += 2 * k) {
let i = start;
let j = Math.min(start + k, t.length) - 1;
while (i < j) {
[t[i], t[j]] = [t[j], t[i]];
i++;
j--;
}
}
return t.join('');
};function reverseStr(s: string, k: number): string {
const t = s.split('');
for (let start = 0; start < t.length; start += 2 * k) {
let i = start;
let j = Math.min(start + k, t.length) - 1;
while (i < j) {
[t[i], t[j]] = [t[j], t[i]];
i++;
j--;
}
}
return t.join('');
}