Domain 1EasyCORE

Reverse String II

The problem requires us to reverse every `k` characters in a string `s`, but only for the first `2k` characters of the string. If there are fewer than `k` characters left, we reverse all of them. If there are between `k` and `2k` characters left, we reverse the first `k` characters and leave the rest as they are.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

541. Reverse String II

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 49.5%


Problem Breakdown

The problem requires us to reverse every k characters in a string s, but only for the first 2k characters of the string. If there are fewer than k characters left, we reverse all of them. If there are between k and 2k characters left, we reverse the first k characters and leave the rest as they are.

Inputs:

  • A string s
  • An integer k

Outputs:

  • The modified string after reversing every k characters in chunks of 2k.

Implicit Constraints or Edge Cases:

  • If k is greater than or equal to the length of the string, we reverse the entire string.
  • If the string length is less than k, we reverse the entire string.
  • If the string length is between k and 2k, we reverse the first k characters.

Intuition

A brute-force approach would involve iterating through the string in chunks of 2k and reversing the first k characters in each chunk. However, this approach might not be optimal in terms of time complexity if the string is very large.

The key insight is to recognize that we can use a two-pointer technique to reverse the required segments of the string efficiently. This avoids unnecessary operations and reduces the overall complexity.

Approach

  1. Convert the string s into a list of characters since strings are immutable in Python.
  2. Iterate through the string in steps of 2k.
  3. For each segment, use two pointers to reverse the first k characters.
  4. Continue this process until the end of the string.
  5. Join the list back into a string and return it.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string. We iterate through the string once, and reversing each segment takes linear time relative to its size.
  • Space Complexity: O(n), due to the additional space required for the list of characters.

Solution

def reverseStr(s: str, k: int) -> str:
    # Convert the string to a list of characters
    s = list(s)
    
    # Iterate through the string in steps of 2k
    for i in range(0, len(s), 2 * k):
        # Reverse the first k characters in the current segment
        left, right = i, min(i + k - 1, len(s) - 1)
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1
    
    # Join the list back into a string and return it
    return ''.join(s)

Edge Cases Handled

  • Edge Case: If k is greater than or equal to the length of the string, we reverse the entire string.
  • Edge Case: If the string length is less than k, we reverse the entire string.
  • Edge Case: If the string length is between k and 2k, we reverse the first k characters.

The solution provided is correct, efficient, and clear. It handles all edge cases as described in the problem statement. The time complexity is O(n), which is optimal for this problem, and the space complexity is also O(n) due to the list conversion.