We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Reverse String II

Number: 541

Difficulty: Easy

Paid? No

Companies: Google, Microsoft, Bloomberg

Problem Description

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 at least k but less than 2k characters left, reverse the first k characters and leave the rest as is.

Key Insights

  • Process the string in chunks of 2k characters.
  • Reverse only the first k characters in each chunk.
  • Handle edge cases where the remaining characters are less than k or between k and 2k.
  • Use slicing (or two pointers) to simplify the reversing process.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string, as we traverse the string in fixed-size steps. Space Complexity: O(n) in the worst case if strings are immutable, since we construct a new string or use an auxiliary array.

Solution

We iterate over the string in increments of 2k. For each segment, we reverse the first k characters. If the remaining substring is shorter than k, we simply reverse all of its characters. The solution uses basic string manipulation techniques such as slicing or in-place reversal with two pointers. The main trick is correctly handling the different lengths of the final segment.

Code Solutions

# Function to reverse a string segment as per specification.
def reverseStr(s: str, k: int) -> str:
    # Convert the string to a list of characters as strings are immutable in Python.
    s_list = list(s)
    n = len(s_list)
    
    # Process the string in increments of 2k.
    for i in range(0, n, 2 * k):
        # Determine the ending index: if not enough characters, take the rest.
        j = min(i + k - 1, n - 1)
        # Reverse characters between indices i and j.
        left, right = i, j
        while left < right:
            s_list[left], s_list[right] = s_list[right], s_list[left]
            left += 1
            right -= 1
    
    # Join the modified list back into a string.
    return ''.join(s_list)

# Example usage:
# print(reverseStr("abcdefg", 2))  # Output: "bacdfeg"
← Back to All Questions