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 <= 104
- s consists of only lowercase English letters.
- 1 <= k <= 104
My Solution
We can solve this problem with a StringBuilder that we initialize to s. We iterate through s, skipping 2k steps at a time. At each iteration we use the two pointer technique to reverse k characters. One detail is that we need to handle the case where there could be fewer than k characters left to reverse. To handle this case, our second pointer y, will point to the smaller index of the last character in the string and the last character in the window of k characters. We swap the characters at the two pointers and increment x and decrement y until x >= y. Finally we just convert the resulting StringBuilder to String and return.
Time complexity is O(n) due to iterating through the string, where n is the length of the String s. Space complexity is also O(n) due to the space required for the StringBuilder.
class Solution {
public String reverseStr(String s, int k) {
StringBuilder sb = new StringBuilder(s);
int n = s.length();
for (int i = 0; i < n; i += 2*k) {
int x = i;
int y = Math.min(x+k-1, n-1);
while (x < y) {
char c = sb.charAt(x);
sb.setCharAt(x, sb.charAt(y));
sb.setCharAt(y, c);
x++;
y--;
}
}
return sb.toString();
}
}