Reverse String II — Solution in Python, Java & C++
Reverse String II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Reverse String II is an easy coding problem on strings and two pointers, asked in Amazon, TCS and Capgemini interviews.
- Difficulty: Easy
- Topics: Strings, Two Pointers
- Asked at: Amazon, TCS, Capgemini
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string s and an integer k, reverse the first k characters of every 2k characters, counting from the start.
If fewer than k characters remain, reverse all of them. If at least k but fewer than 2k remain, reverse the first k and leave the rest alone.
Example 1
Input: s = "codekairo", k = 2
Output: ocdeakiro
Explanation: Taking blocks of four — "code", "kair", "o" — the first two characters of each are reversed: "co" -> "oc" and "ka" -> "ak".
Example 2
Input: s = "abcdefg", k = 2
Output: bacdfeg
Example 3
Input: s = "abcd", k = 4
Output: dcba
Constraints
1 <= s.length <= 100001 <= k <= 10000s consists of lowercase English letters.
Hints for Reverse String II
Hint 1
Step through the string in strides of
2k, not one character at a time.Hint 2
Within each stride, reverse from
itomin(i + k - 1, n - 1).Hint 3
Clamping the right end is what handles both tail cases in the statement at once.
How to solve Reverse String II
The rule is periodic with period 2k: reverse the first half of each period and skip the second. Clamping the reversal's right end to the last index absorbs both special cases the statement spells out.
Approach
- Copy the string into a mutable character array.
- Loop
i = 0, 2k, 4k, …. - Reverse the slice from
itomin(i + k - 1, n - 1)with two pointers. - Join the array back into a string.
Why it works
When at least k characters remain the clamp does nothing and exactly k are reversed; when fewer remain the clamp stops at the end and the whole tail is reversed — which is precisely what the two tail rules ask for.
Complexity
- Time —
O(n) - Space —
O(n) for the character array
Pitfalls
- Stepping by
kinstead of2kreverses the blocks that should be left alone. - Forgetting the clamp reads past the end on the final partial block.
Reference solution
Python
def reverseStr(s: str, k: int) -> str:
a = list(s)
for i in range(0, len(a), 2 * k):
lo, hi = i, min(i + k - 1, len(a) - 1)
while lo < hi:
a[lo], a[hi] = a[hi], a[lo]
lo += 1
hi -= 1
return "".join(a)Java
public static String reverseStr(String s, int k) {
char[] a = s.toCharArray();
for (int i = 0; i < a.length; i += 2 * k) {
int lo = i, hi = Math.min(i + k - 1, a.length - 1);
while (lo < hi) {
char t = a[lo];
a[lo] = a[hi];
a[hi] = t;
lo++;
hi--;
}
}
return new String(a);
}C++
string reverseStr(string s, int k) {
int n = (int) s.size();
for (int i = 0; i < n; i += 2 * k) {
int lo = i, hi = min(i + k - 1, n - 1);
while (lo < hi) {
swap(s[lo], s[hi]);
lo++;
hi--;
}
}
return s;
}JavaScript
var reverseStr = function(s, k) {
var a = s.split("");
for (var i = 0; i < a.length; i += 2 * k) {
var lo = i, hi = Math.min(i + k - 1, a.length - 1);
while (lo < hi) {
var t = a[lo];
a[lo] = a[hi];
a[hi] = t;
lo++;
hi--;
}
}
return a.join("");
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Two Pointers Technique