LeetCode 541 - Reverse String II

Difficulty: 🟢 Easy
Topics: Two Pointers, String

Solution

Problem Understanding

The problem requires us to manipulate a string s in a structured way. Specifically, we need to reverse the first k characters for every consecutive block of 2k characters in the string. If a block has fewer than k characters, we reverse all of them. If a block has between k and 2k characters, we reverse the first k and leave the remaining characters as they are.

The input is a string s containing only lowercase English letters and an integer k. The output is the transformed string after performing the specified reversals.

The constraints tell us that the string length can be up to 10^4 and k can also be up to 10^4. This suggests that we need a solution that is linear in time relative to the string length, and we should be careful about extra space usage.

Important edge cases include a string shorter than k, a string length that is not a multiple of 2k, and when k equals the length of the string. These edge cases could break naive implementations that do not check boundaries carefully.

Approaches

The brute-force approach would be to iterate through the string in chunks of 2k, explicitly reverse the first k characters for each chunk, and concatenate the results to form the final string. This approach is correct but involves unnecessary slicing and string concatenations, which can be inefficient for large strings.

The optimal approach is based on the observation that we can convert the string to a mutable list of characters and reverse sections in place using two pointers. By iterating through the string with a step of 2k, we reverse only the first k characters of each segment. This avoids repeated string concatenation and reduces the overhead of constructing intermediate strings.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n*k)	O(n)	Iterate over chunks, reverse each slice, concatenate strings
Optimal	O(n)	O(n)	Convert to list, reverse in place using two pointers

Algorithm Walkthrough

Convert the string s into a list of characters, because strings are immutable in Python and we need in-place modification.
Iterate over the string with a step size of 2k, starting from index 0.
For each iteration, identify the start and end of the segment to reverse. The segment starts at the current index i and ends at i + k - 1, but must not exceed the string length.
Use two pointers to reverse the segment in place: one pointer at the start and one at the end, swapping characters while moving the pointers toward each other.
Continue until the end of the string is reached.
Convert the list of characters back into a string and return it.

Why it works: By reversing only the first k characters of each 2k block in place, the algorithm satisfies the problem requirement for every segment. The two-pointer reversal guarantees that characters within each segment are reversed efficiently without affecting other segments.

Python Solution

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        chars = list(s)
        n = len(chars)
        
        for i in range(0, n, 2*k):
            left = i
            right = min(i + k - 1, n - 1)
            
            while left < right:
                chars[left], chars[right] = chars[right], chars[left]
                left += 1
                right -= 1
        
        return ''.join(chars)

The implementation first converts the string into a list to allow in-place swapping. The loop increments by 2k because we process blocks of 2k characters at a time, reversing only the first k. The min function ensures we do not exceed the string length. Finally, the list is joined back into a string.

Go Solution

func reverseStr(s string, k int) string {
    chars := []rune(s)
    n := len(chars)
    
    for i := 0; i < n; i += 2 * k {
        left := i
        right := i + k - 1
        if right >= n {
            right = n - 1
        }
        
        for left < right {
            chars[left], chars[right] = chars[right], chars[left]
            left++
            right--
        }
    }
    
    return string(chars)
}

In Go, we convert the string to a []rune to handle Unicode safely, although for lowercase English letters []byte would also suffice. The logic mirrors Python, using two pointers to reverse the segment in place.

Worked Examples

Example 1: s = "abcdefg", k = 2

Iteration	i	Segment to reverse	Resulting string
1	0	"ab"	"bacdefg"
2	4	"ef"	"bacdfe g" → "bacdfeg"

Example 2: s = "abcd", k = 2

Iteration	i	Segment to reverse	Resulting string
1	0	"ab"	"bacd"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate through each character at most once, performing constant-time swaps.
Space	O(n)	We create a list of characters to allow in-place modifications.

The complexity is linear in the length of the string. Converting the string to a list does require O(n) extra space, but the in-place reversal avoids additional overhead.

Test Cases

# test cases
assert Solution().reverseStr("abcdefg", 2) == "bacdfeg"  # example 1
assert Solution().reverseStr("abcd", 2) == "bacd"       # example 2
assert Solution().reverseStr("a", 1) == "a"             # single character
assert Solution().reverseStr("ab", 3) == "ba"           # k > length
assert Solution().reverseStr("abcde", 2) == "bacde"     # 2k > length
assert Solution().reverseStr("abcdefgh", 4) == "dcbahgfe" # full reversal in two 2k blocks

Test	Why
"abcdefg", 2	Basic functionality
"abcd", 2	Small even-length string
"a", 1	Minimum length string
"ab", 3	k larger than string length
"abcde", 2	Partial last block
"abcdefgh", 4	Full reversal in multiple blocks

Edge Cases

One important edge case is when the string length is less than k. In this case, the entire string must be reversed. The implementation handles this with the min function for the right pointer, ensuring no out-of-bounds access.

Another edge case occurs when the string length is between k and 2k. Here, only the first k characters are reversed, and the rest remain unchanged. The step of iterating with 2k ensures this behavior naturally.

Finally, when k equals the string length, the whole string is reversed exactly once. The two-pointer logic correctly identifies the segment and reverses it without exceeding the string boundary. This ensures that all scenarios dictated by the problem statement are handled efficiently.