Leetcode – Reverse String II Solution in Python

Spread the love

Introduction

In the domain of string manipulation problems, the Reverse String II problem stands as an engaging challenge that requires an understanding of both strings and slicing techniques in Python. This problem gives an opportunity to apply elementary programming concepts to achieve a slightly twisted objective. In this comprehensive article, we will dissect the Reverse String II problem, comprehend the underlying logic, and explore various approaches to solve it using Python.

The Reverse String II problem on Leetcode is described as:

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 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 others as is.

For example:

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

Approach 1: Naive String Concatenation

One naive approach to solving this problem is to iterate through the string in chunks of 2k characters, reverse the first k characters of each chunk, and then concatenate them to form the output string.

Here’s a Python code for this approach.

def reverseStr(s, k):
    # Initialize output string
    output = ""
    
    # Iterate through string in chunks of 2k
    for i in range(0, len(s), 2*k):
        # Get the current chunk
        chunk = s[i:i+2*k]
        
        # Reverse the first k characters
        reversed_chunk = chunk[:k][::-1] + chunk[k:]
        
        # Concatenate to output string
        output += reversed_chunk
        
    return output

This approach has a time complexity of O(n), where n is the length of the string, but it is not space efficient due to repeated string concatenation.

Approach 2: Using a List to Store Chunks

Instead of using string concatenation, which can be expensive in terms of time complexity due to the creation of new strings, we can use a list to store each modified chunk and then join them at the end.

Here’s a Python code for this approach.

def reverseStr(s, k):
    # Initialize a list to store the chunks
    chunks = []
    
    # Iterate through string in chunks of 2k
    for i in range(0, len(s), 2*k):
        # Get the current chunk
        chunk = s[i:i+2*k]
        
        # Reverse the first k characters
        reversed_chunk = chunk[:k][::-1] + chunk[k:]
        
        # Append to the list
        chunks.append(reversed_chunk)
    
    # Join the chunks to form the output string
    return "".join(chunks)

This approach also has a time complexity of O(n), but is more space efficient and faster in practice due to the avoidance of repeated string concatenation.

Approach 3: In-place String Manipulation using a List

We can make our solution even more efficient by doing the string manipulation in-place using a list. This involves converting the string to a list, performing the reversals in-place, and then joining the list to form the output string.

Here’s the Python code for this approach.

def reverseStr(s, k):
    # Convert the string to a list
    s_list = list(s)
    
    # Iterate through list in chunks of 2k
    for i in range(0, len(s_list), 2*k):
        # Reverse the first k characters in-place
        s_list[i:i+k] = reversed(s_list[i:i+k])
        
    # Join the list to form the output string
    return "".join(s_list)

This approach also has a time complexity of O(n), and is the most space-efficient and fastest of the three approaches discussed.

Conclusion

In this detailed article, we delved into the Reverse String II problem on Leetcode. We explored three approaches, ranging from a naive string concatenation method to a more optimized in-place manipulation using lists.

Leave a Reply