Reverse String II solution and explanation
Google
Infosys
9 more videos on this problem
Reverse String ii | LeetCode 541 | C++Knowledge Center · 5:34 · 17K views
541. Reverse String-2 || Java || Leetcode || HindiCoding Sphere · 9:15 · 6K views
LeetCode 541 | Reverse String II | Algorithm Explained (Java)Xavier Elon · 6:33 · 6K views
Reverse String II - Solution to LeetCode 541 Reverse String IILEETCODE MASTER · 4:34 · 2K views
Reverse String II | Leetcode 541 | Amazon Google Facebook interview questionSuper Lazy Coder · 9:40 · 1K views
LeetCode 541 | Reverse String II | 2 Pointers | JavaSleepy Cracker · 5:31 · 1K views
541. Reverse String II | Leetcode | PythonAbdullah Arshed · 3:39 · 1K views
344. Reverse String | 541. Reverse String II && LEETCODE EASYcode Explainer · 9:12 · 1K views
Leetcode | Easy | 541. Reverse String II. | Direct | Time: O(N) | JavascriptSoftware Interviews Prep · 9:52 · 338 views
Leetcode 541: Reverse String II in Telugu | Brute Force, Slicing, In-Place | Python DSA | srkcodesSrk Codes · 8:28 · 312 views
The problem
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 <= 104sconsists of only lowercase English letters.1 <= k <= 104
Approach overview
Problem Overview: You are given a string s and an integer k. For every block of 2k characters, reverse the first k characters and keep the next k characters unchanged. If fewer than k characters remain, reverse all of them. If between k and 2k remain, reverse the first k and leave the rest as is.
Approach 1: In-place String Modification (O(n) time, O(1) space)
This approach processes the string in chunks of size 2k. Start from index 0, then move forward in steps of 2k. For each block, reverse the first k characters using a two-pointer technique: one pointer at the start of the block and another at min(start + k - 1, n - 1). Swap characters while moving the pointers toward each other. This ensures only the required portion of each block is reversed.
The key insight is that every 2k window is independent. You never need to touch the second half of the block. Converting the string to a mutable character array allows swaps to happen directly without allocating additional memory. This makes the approach efficient with O(n) time since every character is processed at most once, and O(1) extra space.
This solution relies on simple index manipulation and the two pointers technique, which is common in string and array problems.
Approach 2: String Builder for Efficiency (O(n) time, O(n) space)
Another way is to construct the result using a string builder (or dynamic string). Iterate through the string in steps of 2k. For each iteration, take the first k characters, reverse them explicitly, and append them to the builder. Then append the next k characters in their original order.
This approach avoids modifying the original string and instead builds the answer sequentially. Reversing the substring can be done with a simple loop or a helper function. Because each character is appended exactly once, the total runtime remains O(n). However, the builder stores a new string, so the extra space usage becomes O(n).
This pattern is common in many string manipulation problems where immutability makes in-place edits inconvenient. It can also produce cleaner code in languages where strings cannot be modified directly.
Recommended for interviews: The in-place two-pointer solution is what interviewers typically expect. It demonstrates control over indexing and efficient string manipulation while maintaining O(n) time and O(1) space. The string builder approach still shows correct reasoning and is acceptable when code clarity matters, but the in-place method highlights stronger algorithmic discipline.
Approach 1: Approach 1: In-place String Modification
In this approach, we directly manipulate the string representation by considering it as a character array (or list in some languages) for in-place modification. We handle the string in chunks of 2k and reverse the first k characters of each chunk.
def reverse_string(s, k):
s = list(s) # Convert to list to allow modification
for start in range(0, len(s), 2 * k):
s[start:start + k] = reversed(s[start:start + k])
return ''.join(s)
s = "abcdefg"
k = 2
print(reverse_string(s, k)) # Output: "bacdfeg"public class Main {
public static void reverseString(char[] s, int k) {
for (int start = 0; start < s.length; start += 2 * k) {
int i = start, j = Math.min(start + k - 1, s.length - 1);
while (i < j) {
char temp = s[i];
s[i++] = s[j];
s[j--] = temp;
}
}
}
public static void main(String[] args) {
String str = "abcdefg";
char[] s = str.toCharArray();
int k = 2;
reverseString(s, k);
System.out.println(new String(s)); // Output: "bacdfeg"
}
}#include <iostream>
#include <string>
#include <algorithm>
void reverseString(std::string& s, int k) {
int n = s.size();
for (int start = 0; start < n; start += 2 * k) {
if (start + k <= n) {
std::reverse(s.begin() + start, s.begin() + start + k);
} else {
std::reverse(s.begin() + start, s.end());
}
}
}
int main() {
std::string s = "abcdefg";
int k = 2;
reverseString(s, k);
std::cout << s; // Output: "bacdfeg"
return 0;
}function reverseString(s, k) {
s = s.split('');
for (let start = 0; start < s.length; start += 2 * k) {
let i = start, j = Math.min(start + k - 1, s.length - 1);
while (i < j) {
[s[i], s[j]] = [s[j], s[i]];
i++;
j--;
}
}
return s.join('');
}
let s = "abcdefg";
let k = 2;
console.log(reverseString(s, k)); // Output: "bacdfeg"#include <stdio.h>
#include <string.h>
void reverseString(char* s, int k) {
int length = strlen(s);
for (int start = 0; start < length; start += 2 * k) {
int i = start, j = (start + k - 1 < length) ? start + k - 1 : length - 1;
while (i < j) {
// Swap characters
char temp = s[i];
s[i++] = s[j];
s[j--] = temp;
}
}
}
int main() {
char s[] = "abcdefg";
int k = 2;
reverseString(s, k);
printf("%s", s); // Output: "bacdfeg"
return 0;
}using System;
public class Solution {
public static void ReverseString(char[] s, int k) {
for (int start = 0; start < s.Length; start += 2 * k) {
int i = start, j = Math.Min(start + k - 1, s.Length - 1);
while (i < j) {
char temp = s[i];
s[i++] = s[j];
s[j--] = temp;
}
}
}
public static void Main() {
string str = "abcdefg";
char[] s = str.ToCharArray();
int k = 2;
ReverseString(s, k);
Console.WriteLine(new String(s)); // Output: "bacdfeg"
}
}In Python, this solution converts the string to a list for easy modification. The slice reversing makes it intuitive to handle the required range, converting back to a string at the end of the process.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), due to list conversion.
Approach 2: Approach 2: String Builder for Efficiency
In this approach, we use a StringBuilder (or equivalent structure in the respective programming languages) to construct the final output. This approach is effective because handling mutable strings directly supports efficient character manipulation operations.
def reverse_string(s, k):
result = []
for start in range(0, len(s), 2 * k):
part1 = s[start:start + k][::-1]
part2 = s[start + k:start + 2 * k]
result.append(part1 + part2)
return ''.join(result)
s = "abcdefg"
k = 2
print(reverse_string(s, k)) // Output: "bacdfeg"public class Solution {
public static String reverseString(String s, int k) {
StringBuilder sb = new StringBuilder(s);
for (int start = 0; start < s.length(); start += 2 * k) {
int end = Math.min(start + k, s.length());
sb.replace(start, end, new StringBuilder(s.substring(start, end)).reverse().toString());
}
return sb.toString();
}
public static void main(String[] args) {
String s = "abcdefg";
int k = 2;
System.out.println(reverseString(s, k)); // Output: "bacdfeg"
}
}#include <iostream>
#include <string>
#include <algorithm>
std::string reverseString(const std::string& s, int k) {
std::string result = s;
for (size_t start = 0; start < result.size(); start += 2 * k) {
auto end = std::min(start + k, result.size());
std::reverse(result.begin() + start, result.begin() + end);
}
return result;
}
int main() {
std::string s = "abcdefg";
int k = 2;
std::cout << reverseString(s, k); // Output: "bacdfeg"
return 0;
}function reverseString(s, k) {
let result = '';
for (let start = 0; start < s.length; start += 2 * k) {
let end = Math.min(start + k, s.length);
let reversedPart = s.slice(start, end).split('').reverse().join('');
result += reversedPart + s.slice(end, start + 2 * k);
}
return result;
}
let s = "abcdefg";
let k = 2;
console.log(reverseString(s, k)); // Output: "bacdfeg"#include <stdio.h>
#include <string.h>
void reverseSubString(char* s, int start, int end) {
while (start < end) {
char tmp = s[start];
s[start++] = s[end];
s[end--] = tmp;
}
}
char* reverseString(char* s, int k) {
int length = strlen(s);
for (int i = 0; i < length; i += 2 * k) {
reverseSubString(s, i, (i + k - 1 < length) ? i + k - 1 : length - 1);
}
return s;
}
int main() {
char s[] = "abcdefg";
int k = 2;
printf("%s", reverseString(s, k)); // Output: "bacdfeg"
return 0;
}using System;
using System.Text;
public class Solution {
public static string ReverseString(string s, int k) {
var stringBuilder = new StringBuilder(s);
for (int start = 0; start < s.Length; start += 2 * k) {
int end = Math.Min(start + k, s.Length);
string reversedPart = new string(s.Substring(start, end - start).ToCharArray().Reverse().ToArray());
stringBuilder.Remove(start, end - start).Insert(start, reversedPart);
}
return stringBuilder.ToString();
}
public static void Main() {
string s = "abcdefg";
int k = 2;
Console.WriteLine(ReverseString(s, k)); // Output: "bacdfeg"
}
}This Python approach builds the final string using a list result, reversing the chunks manually using slicing and efficiently joining the parts. This keeps code elegant while avoiding intermediate string concatenations.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n) because of using a list to store parts.
Approach 3: Two Pointers
We can traverse the string s, iterating over every 2k characters, and then use the two-pointer technique to reverse the first k characters among these 2k characters.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.
function reverseStr(s: string, k: number): string {
const n = s.length;
const cs = s.split('');
for (let i = 0; i < n; i += 2 * k) {
for (let l = i, r = Math.min(i + k - 1, n - 1); l < r; l++, r--) {
[cs[l], cs[r]] = [cs[r], cs[l]];
}
}
return cs.join('');
}func reverseStr(s string, k int) string {
cs := []byte(s)
n := len(cs)
for i := 0; i < n; i += 2 * k {
for l, r := i, min(i+k-1, n-1); l < r; l, r = l+1, r-1 {
cs[l], cs[r] = cs[r], cs[l]
}
}
return string(cs)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: In-place String Modification | Time Complexity: O(n), where n is the length of the string. |
| Approach 2: String Builder for Efficiency | Time Complexity: O(n), where n is the length of the string. |
| Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| In-place String Modification | O(n) | O(1) | Best for interviews and memory‑efficient solutions where the string can be converted to a mutable array |
| String Builder for Efficiency | O(n) | O(n) | Useful when strings are immutable or when clearer step‑by‑step construction is preferred |
Frequently asked questions
Is Reverse String II easy or hard?
Reverse String II is classified as an Easy problem. The challenge lies in carefully handling index boundaries and partial segments when fewer than k or 2k characters remain. Once the 2k iteration pattern is understood, the implementation is straightforward.
Reverse String II Python/Java solution
In Python, convert the string to a list of characters and reverse segments using index swaps. In Java, convert the string to a char array and apply the same two-pointer logic. Both implementations follow the same O(n) time algorithm with segment jumps of 2k.
How to solve Reverse String II in O(n)?
Process the string in intervals of 2k. For each starting index i, reverse the substring from i to min(i + k - 1, n - 1) using two pointers that swap characters inward. Then jump to i + 2k and repeat until the string ends.
What is the best approach for Reverse String II?
The most efficient approach is the in-place two-pointer method. Iterate through the string in steps of 2k and reverse only the first k characters of each block. This runs in O(n) time and uses O(1) extra space since swaps happen directly on a character array.
Is Reverse String II asked at Google/Amazon/Meta?
String manipulation and two-pointer problems like Reverse String II frequently appear in coding interviews at companies such as Amazon, Google, and Meta. While the exact question may vary, the pattern of reversing segments and handling edge cases is common in interview rounds.
What data structure is used in Reverse String II?
The main structure used is a mutable character array derived from the input string. The algorithm then applies the two-pointer technique to swap characters within the required range. Some implementations also use a string builder when constructing a new result string.
What is the time complexity of Reverse String II?
The time complexity is O(n), where n is the length of the string. Each character is visited at most once while reversing segments of length k in every 2k block. No nested loops scale with n, so the runtime remains linear.