Reverse String II

Easy
630.

Reverse String II

Reverse String II is an easy coding problem on strings and two pointers, asked in Amazon, TCS and Capgemini interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var reverseStr = function(s, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Hints for Reverse String II

  1. Hint 1

    Step through the string in strides of 2k, not one character at a time.

  2. Hint 2

    Within each stride, reverse from i to min(i + k - 1, n - 1).

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

  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)

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