Reverse String II

LeetCode 541: Reverse String II Solution & Explanation

Problem Overview

TL;DR: The optimal solution iterates through the string in steps of 2k, applying a standard two-pointer reversal technique to the first k characters of each segment while handling boundary checks for the end of the string.

LeetCode 541 requires modifying a string s by reversing specific segments based on a parameter k. The rule dictates that for every block of 2k characters, only the first k characters should be reversed. If fewer than k characters remain at the end, all of them must be reversed. This problem tests the ability to manipulate string indices and implement partial reversals correctly.

Brute Force Approach for Reverse String II

A naive or brute force approach typically involves constructing a new result string by manually slicing and concatenating substrings. The algorithm might attempt to iterate character by character or chunk by chunk, creating temporary string objects for every segment.

Naive Logic:

1. Create an empty result string (or StringBuilder).
2. Loop through the string.
3. Extract the substring of length k.
4. Create a reversed copy of that substring and append it.
5. Extract the next substring of length k (the part that shouldn't be reversed).
6. Append it as-is.
7. Repeat until the end, adding complex conditional logic to handle the final remaining characters.

Why this is suboptimal: While this approach generally results in $O(N)$ time complexity, it suffers from poor space efficiency and code complexity. In languages with immutable strings (like Java or Python), creating multiple substring instances generates excessive garbage for the memory collector. Furthermore, the logic often becomes cluttered with if-else statements to handle the "fewer than k" or "between k and 2k" constraints, increasing the likelihood of off-by-one errors.

Algorithm Strategy: Two Pointer Patterns

1. Convert to Mutable Structure: Since strings are immutable in many languages (Java, Python), first convert the input string s into a mutable character array or list.
2. Step-wise Iteration: Initialize a loop that starts at index 0 and increments by 2k in each iteration. This handles the "every 2k characters" requirement naturally.
3. Define Boundaries: Inside the loop, establish the range to be reversed.
   • start pointer is the current loop index i.
   • end pointer is min(i + k - 1, length - 1). This min function automatically handles the case where fewer than k characters remain.
4. Two-Pointer Swap: Perform the reversal on the range [start, end].
   • While start < end:
     • Swap the characters at start and end.
     • Increment start.
     • Decrement end.
5. Reconstruction: Convert the modified mutable structure back into a string and return it.

Execution Flow

Let's trace the algorithm with s = "abcdefg", k = 2. Length n = 7.

1. Initialization: Convert s to ['a', 'b', 'c', 'd', 'e', 'f', 'g'].
2. Iteration 1:
   • i = 0.
   • Calculate end: min(0 + 2 - 1, 6) = min(1, 6) = 1.
   • Reverse range [0, 1] ('a', 'b').
   • Swap arr[0] and arr[1]. Array becomes ['b', 'a', 'c', 'd', 'e', 'f', 'g'].
   • Increment i by 2k (4).
3. Iteration 2:
   • i = 4.
   • Calculate end: min(4 + 2 - 1, 6) = min(5, 6) = 5.
   • Reverse range [4, 5] ('e', 'f').
   • Swap arr[4] and arr[5]. Array becomes ['b', 'a', 'c', 'd', 'f', 'e', 'g'].
   • Increment i by 2k (4). New i is 8.
4. Termination:
   • i = 8 is greater than n = 7. Loop terminates.
5. Result: Convert array to string: "bacdfeg".

Proof of Correctness

The correctness relies on the invariant that for any block starting at index i, we must reverse the sub-segment [i, i+k-1].

1. Standard Case: When i + k <= n, the algorithm reverses exactly k characters. The step size of 2k ensures the next k characters (from i+k to i+2k-1) are skipped, satisfying the problem statement.
2. Edge Case (Remaining < k): When i + k > n, the logic min(i + k - 1, n - 1) clamps the reversal range to the end of the string. This satisfies the condition "If there are fewer than k characters left, reverse all of them."
3. Edge Case (k <= Remaining < 2k): The loop step ensures we process the start of this block. The reversal logic handles the first k, and the subsequent characters are never touched because the loop terminates before processing them (since the next step is i + 2k, which would be out of bounds).

Thus, the algorithm correctly satisfies all conditions via the stride logic and boundary clamping.

Pattern Reuse Notes

The Two Pointers - String Reversal pattern is highly reusable. Understanding how to manipulate start and end pointers to reverse segments is crucial for these related problems:

• LeetCode 151: Reverse Words in a String: Requires reversing the entire string and then reversing individual words (or vice versa), using the exact same subpattern.
• LeetCode 344: Reverse String: The most basic form of this pattern, reversing the entire array in place.
• LeetCode 345: Reverse Vowels of a String: Uses two pointers moving inward, but with a conditional check (isVowel) before swapping.

Reference Implementation

C++ Solution for LeetCode 541

1class Solution {
2public:
3    string reverseStr(string s, int k) {
4        int n = s.length();
5        
6        // Iterate with a step of 2k
7        for (int i = 0; i < n; i += 2 * k) {
8            // Identify the range to reverse.
9            // Start is i, end is either i + k - 1 or the last index of the string.
10            int left = i;
11            int right = min(i + k - 1, n - 1);
12            
13            // Apply Two Pointers - String Reversal subpattern
14            while (left < right) {
15                swap(s[left], s[right]);
16                left++;
17                right--;
18            }
19        }
20        
21        return s;
22    }
23};

Java Solution for LeetCode 541

1class Solution {
2    public String reverseStr(String s, int k) {
3        // Convert to char array because Java Strings are immutable
4        char[] arr = s.toCharArray();
5        int n = arr.length;
6        
7        // Iterate with a step of 2k
8        for (int i = 0; i < n; i += 2 * k) {
9            // Identify the range to reverse
10            int left = i;
11            // Clamp the right boundary to ensure we don't go out of bounds
12            int right = Math.min(i + k - 1, n - 1);
13            
14            // Apply Two Pointers - String Reversal subpattern
15            while (left < right) {
16                char temp = arr[left];
17                arr[left] = arr[right];
18                arr[right] = temp;
19                left++;
20                right--;
21            }
22        }
23        
24        return new String(arr);
25    }
26}

Python Solution for LeetCode 541

1class Solution:
2    def reverseStr(self, s: str, k: int) -> str:
3        # Convert to list because Python strings are immutable
4        s_list = list(s)
5        n = len(s_list)
6        
7        # Iterate with a step of 2k
8        for i in range(0, n, 2 * k):
9            # Identify the range to reverse
10            left = i
11            # Clamp the right boundary
12            right = min(i + k - 1, n - 1)
13            
14            # Apply Two Pointers - String Reversal subpattern
15            while left < right:
16                s_list[left], s_list[right] = s_list[right], s_list[left]
17                left += 1
18                right -= 1
19                
20        return "".join(s_list)