Reverse String II
Problem
Given a string 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 left the other as original. Example:
Input: s = "abcdefg", k = 2
Output: "bacdfeg"
Note: The string consists of lower English letters only. Length of the given string and k will in the range [1, 10000]
Solution
public class Solution {
public String reverseStr(String s, int k) {
if (s == null || k <= 1) return s;
char[] chars = s.toCharArray();
int start = 0, len = s.length();
while (start < len - 1) {
int end = Math.min(start + k - 1, len - 1); //Avoid index out of bounds
reverse(chars, start, end);
start += 2 * k;
}
return String.valueOf(chars);
}
private void reverse(char[] chars, int start, int end) {
while (start < end) {
char temp = chars[start];
chars[start++] = chars[end];
chars[end--] = temp;
}
}
}
Analysis
Typical reversing solution using two-pointer swap
The only difference between this problem and Reverse String is that we have a bound
Which means we need to have a helper method reverse()
with given indices of two ends
We increase the start
index every time finishing the reverse in k
intervals by += 2 * k
Notice that we use Math.min()
to avoid index out of bounds exception