Reverse String II — Easy Problem & Solution

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 <= 10000
• 1 <= k <= 10000
• s consists of lowercase English letters.

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

1. Copy the string into a mutable character array.
2. Loop i = 0, 2k, 4k, ….
3. Reverse the slice from i to min(i + k - 1, n - 1) with two pointers.
4. 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 k instead of 2k reverses 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)

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Find the Original Typed String I Easy
• Rearrange Characters to Make Target String Easy
• Number of Strings That Appear as Substrings in Word Easy
• Circular Sentence Easy
• Number of Senior Citizens Easy
• Find Words Containing Character Easy