Reverse Strings II

Problem

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less 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 left the other as original.

For example:

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

Thought Process

• We can split the string into chuncks of size k so that the necessary contiguous substrings that need to be reversed are already in order

• We can then run through this list of size k chuncks in steps of 2 (because need to reverse the first k characters for every 2k characters) and reverse these ones

Solution

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        
        # Divide s into an array of substrings length k
        s = [s[i:i+k] for i in range(0, len(s), k)]
        
        
        # Reverse every other substring, beginning with s[0]
        for i in range(0, len(s), 2):
            s[i] = s[i][::-1]
            
        # Join array of substrings into one string and return 
        return ''.join(s)
        

Time Complexity

• Time: O(n)

• Space: O(1) because we are manipulating the given string, we use no space for storage.