#541

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Reverse String II

Reverse String II requires reversing segments of a string using two-pointer scanning while tracking invariants carefully.

two pointers string

Problem Statement

Given a string s and an integer k, reverse the first k characters for every consecutive block of 2k characters, keeping the rest in original order. If a block contains fewer than k characters, reverse all of them.

For blocks with at least k but fewer than 2k characters, reverse the first k characters and leave the remaining characters unchanged. Implement this to return the modified string according to the described pattern.

Examples

Example 1

Input: s = "abcdefg", k = 2

Output: "bacdfeg"

Example details omitted.

Example 2

Input: s = "abcd", k = 2

Output: "bacd"

Example details omitted.

Constraints

1 <= s.length <= 104
s consists of only lowercase English letters.
1 <= k <= 104

Solution Approach

Two-Pointer Reversal for Each Block

Initialize two pointers at the start and end of the current k-segment. Swap characters while moving pointers inward. Repeat this for every 2k block until the string ends, ensuring the invariant that only the first k characters are reversed.

Handle Partial Segments Carefully

Check segment lengths before reversing. If fewer than k characters remain, reverse all. If between k and 2k, reverse only the first k. Properly managing the boundaries prevents out-of-range errors.

Iterative Scanning Across the String

Step through the string in increments of 2k, applying the two-pointer reversal logic. This ensures linear O(N) traversal and maintains the exact pattern required by Reverse String II, avoiding unnecessary recursion or extra memory usage.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(N)

Time complexity is O(N) because each character is visited at most once during the swaps. Space complexity is O(N) if using a character array for in-place swaps; otherwise, extra space is minimal beyond the original string.

What Interviewers Usually Probe

Look for proper handling of blocks smaller than k to test boundary understanding.
Ensure the candidate uses two pointers rather than naive slicing to avoid extra memory usage.
Watch if the candidate correctly iterates in 2k steps rather than per-character to maintain efficiency.

Common Pitfalls or Variants

Common pitfalls

Reversing more than k characters in a 2k block and corrupting the second half.
Failing to handle the last partial segment correctly when its length is less than k.
Using string concatenation inside loops, leading to O(N^2) time instead of O(N).

Follow-up variants

Reverse every first k characters in 3k blocks instead of 2k, requiring adjusted pointer increments.
Perform conditional reversal based on character type (e.g., vowels only) while keeping the 2k block pattern.
Apply the same two-pointer invariant logic to an array of integers instead of a string.

FAQ

What is the core pattern in Reverse String II?

The main pattern is two-pointer scanning with invariant tracking, reversing only the first k characters in every 2k block.

How do I handle the last segment if it has fewer than k characters?

Reverse all remaining characters in that segment, ensuring no indices go out of bounds.

Is using extra space necessary for this problem?

No, you can convert the string to a character array and perform in-place swaps using two pointers to maintain O(N) space.

Can this pattern be applied to arrays of numbers?

Yes, the two-pointer invariant reversal approach works for arrays of any elements, not just strings.

Why not reverse the entire 2k block at once?

Reversing the whole block would violate the problem requirement of reversing only the first k characters, producing incorrect output.

terminal

Solution

Solution 1: Two Pointers

We can traverse the string $\textit{s}$, iterating over every $\textit{2k}$ characters, and then use the two-pointer technique to reverse the first $\textit{k}$ characters among these $\textit{2k}$ characters.

1

2

3

4

5

6

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        cs = list(s)
        for i in range(0, len(cs), 2 * k):
            cs[i : i + k] = reversed(cs[i : i + k])
        return "".join(cs)

Continue Practicing

#556 next greater element iii #557 reverse words in a string iii #524 longest word in dictionary through deleting