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"
Restrictions:
- The string consists of lower English letters only.
- Length of the given string and k will in the range [1, 10000]
Refer to the diagram below.
- Tuesday, 25 August, 2020
- Time Complexity: Not sure. Might be
$O(k \times n)$ - Space Complexity:
$O(1)$ - Runtime: 0 ms, faster than 100.00% of C online submissions for Reverse String II.
- Memory Usage: 6.1 MB, less than 100.00% of C online submissions for Reverse String II.
void reverseString(char *s, int head, int tail) {
while (head < tail) {
// Swapping two characters.
int temp = s[head];
s[head] = s[tail];
s[tail] = temp;
head++;
tail--;
}
}
char *reverseStr(char *s, int k) {
// See the diagram for help.
int groups = strlen(s) / (2 * k);
int n = 0;
// Reverse substrings until the remainder less than 2k;
while (n < groups) {
reverseString(s, 2 * k * n, 2 * k * n + k - 1);
n++;
}
// k > remainder;
if (strlen(s) % (2 * k) < k) {
reverseString(s, 2 * k * n, strlen(s) - 1);
// 2k > remainder > k.
} else {
reverseString(s, 2 * k * n, 2 * k * n + k - 1);
}
return s;
}
- Complexity:
$O(n)$ ,$O(k * n)$ or$O(n^{2})$ ?