541. Reverse String II

Problem Definition

LeetCode link: 541. Reverse String II

Given a string s and an integer k, 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 less than 2k but greater than or equal to k characters, then reverse the first k characters and leave the other as original.

Example 1:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

Example 2:

Input: s = "abcd", k = 2
Output: "bacd"

Constraints:

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

Understanding the Pattern

The key to solving this problem elegantly lies in recognizing its pattern. Instead of getting lost in complex character-by-character manipulation, we can leverage the consistent 2k pattern to our advantage.

Let's visualize how this works with the first example where s = "abcdefg" and k = 2:

Original: a b | c d | e f | g
          ↓ ↓ | - - | ↓ ↓ | ↓
Result:   b a | c d | f e | g

The arrows indicate which characters get reversed, showing the pattern of:

• Reverse first 2 characters (k=2)
• Skip next 2 characters
• Repeat

Thought Process

At first glance, you might be tempted to write complex logic or use counters to track each segment and its characters. However, there's a simpler approach.

The key is to recognize that we can process the string in fixed chunks: we move through the string in steps of 2k length, which naturally aligns with the pattern we need to handle. This makes it easy to identify and reverse the appropriate sections without needing elaborate tracking mechanisms.

The main insight here is about efficiently handling string patterns. Rather than checking each character individually, we can use the step size in our loop (i += 2k) to jump directly to the start of each new segment that needs processing. This approach not only simplifies the code but also makes it more efficient since we're only looking at the positions we actually need to modify.

Approach Overview

We will explore multiple Python solutions, demonstrating different techniques to implement this logic efficiently.

Solution 1: Iterative Approach with Manual Reversal

How It Works

This solution uses an explicit function to reverse substrings within the defined rules. The reverse_substring helper function handles in-place reversal of a segment of the string converted to a list.

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        # Helper function to reverse a portion of the list
        def reverse_substring(text):
            left, right = 0, len(text) - 1
            while left < right:
                # Swap characters at left and right pointers
                text[left], text[right] = text[right], text[left]
                # Move pointers towards the center
                left += 1
                right -= 1
            return text

        # Convert string to list for mutability
        res = list(s)
        
        # Process string in chunks of size 2k
        for cur in range(0, len(s), 2 * k):
            # Reverse only the first k characters in each 2k chunk
            res[cur: cur + k] = reverse_substring(res[cur: cur + k])
        
        # Convert back to string
        return ''.join(res)

Complexity Analysis

• Time Complexity: O(n), where n is the length of the string. Each character is visited once.
• Space Complexity: O(n), as a list copy of the string is created.

Solution 2: String Slicing

Overview

Using Python’s slicing features, we can directly modify parts of the string without manually iterating over the characters. This approach is concise and leverages Python’s built-in string manipulation capabilities.

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        result = []
        for i in range(0, len(s), 2*k):
            # Extract the current 2k chunk
            chunk = s[i:i+2*k]
            
            # Reverse first k characters and keep rest as is
            reversed_part = chunk[:k][::-1]  # First k chars reversed
            remaining_part = chunk[k:]       # Rest unchanged
            
            # Combine and add to result
            result.append(reversed_part + remaining_part)
        
        # Join all chunks
        return ''.join(result)

Detailed Explanation:

1. Chunk Processing:
   • Extracts chunks of size 2k using string slicing
   • s[i:i+2*k] gets the current chunk
2. Reversal Operation:
   • chunk[:k][::-1] reverses first k characters
   • The [::-1] is Python's slice notation for reversal
   • chunk[k:] keeps remaining characters unchanged
3. List Building:
   • Builds list of processed chunks
   • More memory efficient than concatenating strings
4. Advantages:
   • Clean, readable code
   • Leverages Python's built-in capabilities
   • No explicit character swapping needed

Complexity Analysis

• Time Complexity: O(n), as each slice operation visits a segment of the string once.
• Space Complexity: O(n), as slicing creates new string segments.

Notes

This approach is elegant and works well for small to medium-sized strings, but it creates intermediate string copies, which may add overhead for very large inputs.

Solution 3: In-Place List Modification

Overview

By converting the string to a list, we can perform in-place modifications without additional slicing overhead. This approach is efficient for cases where space is a concern.

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        # Convert to list once
        chars = list(s)
        
        # Process in 2k chunks
        for i in range(0, len(chars), 2*k):
            # Get the slice to reverse (up to k characters)
            slice_to_reverse = chars[i:i+k]
            
            # Replace slice with its reverse
            chars[i:i+k] = reversed(slice_to_reverse)
            # Note: reversed() is a memory-efficient iterator
        
        # Join characters back into string
        return ''.join(chars)

Detailed Explanation:

1. Single List Conversion:
   • Converts string to list only once at the start
   • Minimizes memory overhead
2. Efficient Reversal:
   • Uses Python's reversed() function
   • Returns an iterator instead of creating new list
   • Memory efficient for large strings
3. Slice Assignment:
   • Directly assigns reversed slice back to original list
   • No need for temporary storage
4. Memory Benefits:
   • Minimal temporary objects created
   • Efficient for large strings
   • In-place modifications where possible

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1) for in-place operations (excluding the output string).

Solution 4: Alternative Iterative Approach

Overview

This solution iteratively processes the string in chunks of 2k without explicitly reversing intermediate slices. It offers another way to implement the logic efficiently.

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        return ''.join(
            # Process each 2k chunk
            (
                # Reverse first k characters
                s[i:i+k][::-1] +
                # Keep next k characters as is
                s[i+k:i+2*k]
            )
            # Generate indices for each 2k chunk
            for i in range(0, len(s), 2*k)
        )

Detailed Explanation:

1. Generator Expression:
   • Uses generator for memory efficiency
   • Processes one chunk at a time
2. Chunk Processing:
   • s[i:i+k][::-1]: Reverses first k characters
   • s[i+k:i+2*k]: Keeps next k characters unchanged
3. String Building:
   • join() combines all chunks efficiently
   • Avoids intermediate string concatenations
4. Benefits:
   • Most concise solution
   • Memory efficient due to generator
   • No explicit loops or temporary variables

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n), due to the list conversion of the string.

Key Takeaways

1. Choosing Between Approaches:

• Use Classic Approach for learning and interviews
• Use String Slicing for quick prototyping
• Use Memory-Efficient for large strings
• Use Functional for clean, maintainable code

2. Common Pitfalls:

• Forgetting string immutability
• Inefficient string concatenation
• Not handling edge cases properly
• Over-complicated chunk calculations