Reverse String Ii - Leetcode Solution

Problem Statement:

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

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

Explanation: First 2 characters are "ab" and their reverse is "ba". Next 2 characters are "cd" and they are not reversed. Next 2 characters are "ef" and their reverse is "fe". Last character is "g" and it is not reversed.

Solution:

The problem statement asks us to reverse the first k characters for every 2k characters in the given string s. We will iterate over the string s and at every 2k characters, we will reverse the first k characters. To handle the case when the remaining characters are less than k, we will reverse all of them. And to handle the case when the remaining characters are less than 2k but greater than or equal to k characters, we will reverse the first k characters and leave the others as is.

We will use a loop to iterate over the string s. We will use an index variable i to keep track of the current position in the string s. We will initialize i to 0 and will increment it by 2k in every iteration. Inside the loop, we will reverse the first k characters from the current position i. We will use the Python slice notation s[i:i+k] to get the first k characters from the string s starting at index i. We will then reverse these characters using the built-in Python function reversed(). We will use the Python slice notation s[:i] to get the string s up to index i-1. We will use the Python slice notation s[i+k:] to get the remaining part of the string s after the reversed part. We will then concatenate these three parts to get the final string after every 2k characters.

To handle the cases when there are less than k characters left, we will reverse all of them. To handle the cases when there are less than 2k but greater than or equal to k characters left, we will reverse the first k characters and leave the others as is. We will use the min() function to get the minimum of k and len(s)-i. This will give us the number of characters that we need to reverse at the current position i.

Python Code:

def reverseStr(s, k): res = "" i = 0 while i < len(s): revStr = s[i:i+k] if (i / (2k)) % 2 == 0: res += revStr[::-1] else: res += revStr res += s[i+k:min(i+2k, len(s))] i += 2*k return res

Explanation:

We have defined a function reverseStr() that takes two arguments s and k. We have initialized an empty string res to store the reversed string. We have initialized the index variable i to 0 and used a while loop to iterate over the string s. We have used the condition i < len(s) to ensure that we do not go beyond the end of the string s.

Inside the loop, we have defined a variable revStr to get the first k characters from the string s starting at the current position i using the Python slice notation s[i:i+k]. We have used the if condition (i / (2*k)) % 2 == 0 to check if we need to reverse the characters at the current position i. This condition checks if i is at an even multiple of 2k and if so, we reverse the characters at that position.

We have used the Python slice notation revStr[::-1] to reverse the characters in revStr. We have then used the += operator to concatenate the reversed string revStr with the result string res.

We have used the else condition to handle the case when we do not need to reverse the characters at the current position i. In this case, we simply concatenate the string revStr with the result string res using the += operator.

We have then used the Python slice notation s[i+k:min(i+2*k, len(s))] to get the remaining part of the string s after the reversed part. We have used the min() function to ensure that we do not go beyond the end of the string s and that we handle the cases when there are less than k characters left or when there are less than 2k but greater than or equal to k characters left.

We have then concatenated the three parts revStr (reversed or not), the remaining part after the reversed part, and the current result string res to get the final string.

We have incremented the index variable i by 2k in every iteration to move to the next position to reverse the characters.

We have returned the final result string res when the loop is done.

Time Complexity:

The time complexity of this solution is O(n/k) where n is the length of the string s and k is the given integer. This is because we are iterating over the string s in steps of 2k and reversing k characters at every 2k characters, which gives us n/k iterations. The time complexity of reversing k characters is O(k) and concatenating strings is also O(k), which gives us a total time complexity of O(k) per iteration. Therefore, the total time complexity of the solution is O(n/k * k) = O(n).

Thus, we have given a detailed solution to the Reverse String II problem on LeetCode.

1