Skip to main content

Reverse String II

Problem 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.

Examples​

Example 1:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

Example 2:

Input: s = "abcd", k = 2
Output: "bacd"

Constraints​

  • 1≤s.length≤1041 \leq s.length \leq 10^4
  • s consists of only lowercase English letters.
  • 1≤k≤1041 \leq k \leq 10^4

Solution for Reverse String II​

Approach​

Intuition and Algorithm​

We will reverse each block of 2k characters directly.

Each block starts at a multiple of 2k: for example, 0, 2k, 4k, 6k, .... One thing to be careful about is we may not reverse each block if there aren't enough characters.

To reverse a block of characters from i to j, we can swap characters in positions i++ and j--.

Code in Different Languages​

Written by @Shreyash3087
#include <iostream>
#include <string>
#include <algorithm>

class Solution {
public:
std::string reverseStr(std::string s, int k) {
for (int start = 0; start < s.length(); start += 2 * k) {
int i = start;
int j = std::min(start + k - 1, static_cast<int>(s.length()) - 1);
while (i < j) {
std::swap(s[i++], s[j--]);
}
}
return s;
}
};

Complexity Analysis​

Time Complexity: O(N)O(N)​

Reason: where N is the size of s. We build a helper array, plus reverse about half the characters in s.

Space Complexity: O(N)O(N)​

Reason: the size of a.

References​


Authors:

Loading...