Problem Overview

You are given a string s and an integer k.
Your task is to reverse the first k characters for every 2k characters in the string.

In other words:

• For every segment of length 2k, reverse the first k characters and leave the next k characters as they are.
• If there are fewer than k characters left, reverse all of them.
• If there are between k and 2k characters, reverse the first k and leave the rest.

Example 1:

Input: s = "abcdefg", k = 2  
Output: "bacdfeg"
Explanation:
- Reverse first 2 → "ba"
- Next 2k range = "cd" remains unchanged
- Next 2k range = "efg" → reverse first 2 → "fe", last "g" unchanged

Example 2:

Input: s = "abcd", k = 2  
Output: "bacd"
Explanation:
- Reverse first 2 → "ba"
- Next 2k segment doesn’t exist, so stop.

---

Intuition / Approach

We can solve this problem efficiently by iterating through the string in chunks of 2k characters.
For every chunk:

• Identify the range [i, i + k - 1] that should be reversed.
• Reverse that range in-place (using a helper method or manual swapping).

We don’t need to touch characters beyond the end of the string if there are fewer than k remaining.

---

Algorithm Explanation

1. Convert the input string s to a character array since strings are immutable in Java.
2. Iterate over the array with a step of 2k:
   • For each position i, determine the start index i and the end index i + k - 1.
   • If i + k - 1 exceeds the array length, set the end index to s.length - 1.
3. Reverse the characters in the identified range [i, end].
4. After processing all segments, convert the character array back to a string and return it.

---

Java Code Implementation

public class ReverseStringII {
    
    public String reverseStr(String s, int k) {
        char[] arr = s.toCharArray();
        int n = arr.length;

        // Process every 2k block
        for (int i = 0; i < n; i += 2 * k) {
            int left = i;
            int right = Math.min(i + k - 1, n - 1);
            reverse(arr, left, right);
        }

        return new String(arr);
    }

    // Helper method to reverse part of the array in place
    private void reverse(char[] arr, int left, int right) {
        while (left < right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }

    // Example usage
    public static void main(String[] args) {
        ReverseStringII solution = new ReverseStringII();
        String s = "abcdefg";
        int k = 2;
        System.out.println(solution.reverseStr(s, k));  // Output: "bacdfeg"
    }
}

---

Complexity Analysis

Time Complexity:

• Each character is visited at most once while performing swaps.
• Therefore, time complexity is O(n), where n is the length of the string.

Space Complexity:

• We use a constant amount of extra space (a few variables and temporary swaps).
• Hence, space complexity is O(1) (excluding the character array since it’s derived from the string).

---

Alternative Approaches

1. Using StringBuilder (less optimal):
   You could use StringBuilder and manually append reversed substrings.
   However, this approach is less efficient since creating new substrings increases time complexity to O(n²).
2. Recursive Approach:
   You could recursively process segments of size 2k, reversing the first k characters each time.
   But recursion adds extra function call overhead and isn’t necessary here.