Code Implementation

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

class Solution {
public:
    string reverseStr(string s, int k) {
        int n = s.size();
        for (int i = 0; i < n; i += 2 * k) {
            int left = i;
            int right = min(i + k - 1, n - 1);
            while (left < right) {
                swap(s[left++], s[right--]);
            }
        }
        return s;
    }
};
      

class Solution {
    public String reverseStr(String s, int k) {
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i += 2 * k) {
            int left = i;
            int right = Math.min(i + k - 1, arr.length - 1);
            while (left < right) {
                char temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left++;
                right--;
            }
        }
        return new String(arr);
    }
}
      

var reverseStr = function(s, k) {
    let arr = s.split('');
    for (let i = 0; i < arr.length; i += 2 * k) {
        let left = i, right = Math.min(i + k - 1, arr.length - 1);
        while (left < right) {
            [arr[left], arr[right]] = [arr[right], arr[left]];
            left++;
            right--;
        }
    }
    return arr.join('');
};
      

Problem Description

You are given a string s and an integer k. The task is to reverse the first k characters for every 2k characters counting from the start of the string. If there are fewer than k characters left, reverse all of them. If there are between k and 2k characters, reverse the first k characters and leave the rest as is.

• Each character in s is a lowercase English letter.
• 1 ≤ s.length ≤ 10⁴
• 1 ≤ k ≤ 10⁴

The solution must process the string according to the above rules and return the resulting string. Each character should be used exactly once and not reused.

Thought Process

The problem asks us to reverse segments of the string in a repeating pattern. At first, it might seem complicated, but if we break the string into chunks of 2k, we can see a clear pattern: in each chunk, only the first k characters are reversed, and the next k characters are left as is. If the chunk is smaller than 2k, we adjust accordingly.

A brute-force approach would be to create substrings for every 2k block and process them separately, but this would be inefficient for large strings. Instead, we can work directly on the character array, reversing in-place for better performance.

The key is to move through the string in steps of 2k, reversing only the first k characters in each step, and leaving the rest untouched. If we reach the end and there are fewer than k characters, we reverse all remaining characters.

Solution Approach

• Convert the string s to a character array (or mutable string) to allow in-place modifications.
• Iterate over the string with a step size of 2k (i.e., process index 0, 2k, 4k, ...).
• For each step, reverse the substring starting at the current index up to k characters ahead. If there are fewer than k characters left, reverse all remaining characters.
• Leave the next k characters (if any) untouched.
• Repeat the process until the end of the string is reached.
• Finally, convert the character array back to a string and return it.

This approach is efficient because it only scans the string once and does in-place reversals, leading to optimal time and space usage.

We use array slicing and reversing (or manual swaps) because they provide O(1) access and modification, making the algorithm both simple and fast.

Example Walkthrough

Example:
s = "abcdefg", k = 2

1. Divide the string into blocks of 2k = 4:
   - Block 1: "abcd"
   - Block 2: "efg"
2. Block 1 ("abcd"):
   - Reverse the first 2 characters: "ab" → "ba"
   - Result: "bacd"
3. Block 2 ("efg"):
   - Fewer than 2k but more than k characters.
   - Reverse the first 2 characters: "ef" → "fe"
   - Result: "fe" + "g" = "feg"
4. Concatenate the processed blocks: "bacd" + "feg" = "bacdfeg"

At each step, only the first k characters of each 2k block are reversed, as required.

Time and Space Complexity

• Brute-force approach:
  • Time: O(n), because each character is visited at most once.
  • Space: O(n), if new substrings are created for each block.
• Optimized approach (in-place):
  • Time: O(n), as we iterate through the string once, and each reversal is O(k), but the total across the string is still O(n).
  • Space: O(n) in languages with immutable strings (like Python or JavaScript, due to conversion to array), but O(1) extra space if in-place (like C++ with string, or Java with char array).

The algorithm is efficient and suitable for large input sizes.

Summary

The "Reverse String II" problem can be efficiently solved by iterating over the string in chunks of 2k and reversing only the first k characters in each chunk. By working directly with a mutable character array and reversing in-place, we achieve optimal time and space complexity. The approach is simple, direct, and leverages the predictable structure of the problem for an elegant solution.