Leetcode 541. Reverse String II

Problem Explanation

In this problem, we are given a string s and an integer k. Our task is to reverse every first k characters for every 2k characters in the string. If there are less than k characters left, we should reverse all of them. Also, if there are less than 2k but equal or more than k characters, then we will only reverse the first k characters and leave the rest as is.

Let's try this on an example:

Example:

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

Step 1: The first 2k characters are "abcdefg" and k = 2. So, we reverse the first k characters "ab" to get "ba", leaving the rest "cdefg" same, we get "bacdefg". Step 2: We now move on to the next 2k set, but only "cdefg" remains. This is less than 2k but more than or equal to k, so we reverse the first k characters "cd" to get "dc", leaving "efg" same, we now have "bacdfeg" which is the output.

Approach

The approach to solve this problem is straightforward. We will iterate through the string using increments of 2k and reverse the first k characters.

In Python, we can do string slicing to make this simpler. In other languages that do not support string slicing (like C++ and Java), we have to manually swap the characters in the string.

Let's look at the solutions in the following languages: Python, Java, JavaScript, C++ and C#.

Solution in Python

1
2python
3class Solution:
4    def reverseStr(self, s: str, k: int) -> str:
5        s = list(s)
6        for i in range(0, len(s), 2*k):
7            s[i:i+k] = reversed(s[i:i+k])
8        return ''.join(s)

In the above code, we first convert the string s to a list because strings in Python are immutable. Hence, we cannot change individual characters directly. Then we loop through the string with a step size of 2k. For each step, we take the slice up to k and reverse it and then join them back.

Solution in Java

1
2java
3class Solution {
4    public String reverseStr(String s, int k) {
5        char[] arr = s.toCharArray();
6        for (int i = 0; i < arr.length; i += 2*k) {
7            int l = i;
8            int r = Math.min(i + k - 1, arr.length - 1);
9            while (l < r) {
10                char temp = arr[l];
11                arr[l++] = arr[r];
12                arr[r--] = temp;
13            }
14        }
15        return new String(arr);
16    }
17}

In Java, we convert the string to a character array. We use the same logic here but we manually swap the characters because Java doesn't support string slicing.

Solution in JavaScript

1
2javascript
3var reverseStr = function(s, k) {
4    s = s.split('');
5    for(let i = 0; i < s.length; i += 2*k)
6        s.splice(i, k, ...s.splice(i, k).reverse())
7    return s.join('');
8};

In JavaScript, we also convert the string to an array. We make use of the ES6 spread operator and the array's reverse function to make the solution more concise.

Solution in C++

1
2cpp
3class Solution {
4public:
5    string reverseStr(string s, int k) {
6        for (int i = 0; i < s.size(); i += 2*k) {
7            int l = i;
8            int r = min(i + k - 1, (int)s.size() - 1);
9            while (l < r)
10                swap(s[l++], s[r--]);
11        }
12        return s;
13    }
14};

In C++, we directly operate on the string and use a swap function to reverse the characters since C++ supports this operation on strings.

Solution in C#

1
2csharp
3public class Solution {
4    public string ReverseStr(string s, int k) {
5        char[] arr = s.ToCharArray();
6        for (int i = 0; i < arr.Length; i += 2*k) {
7            int l = i;
8            int r = Math.Min(i + k - 1, arr.Length - 1);
9            while (l < r) {
10                char temp = arr[l];
11                arr[l++] = arr[r];
12                arr[r--] = temp;
13            }
14        }
15        return new string(arr);
16    }
17}

In the C# solution, we follow the same approach as Java, first converting the string to a char array and manually swapping the characters.## Summary

Reversing the segments of a string is not direct in certain languages because strings are mostly immutable. Therefore, we need to convert them to another data structure like an array or a list that supports direct modifications.

The main loop iterates over the string s with a step of 2k units. The step of 2k units helps to guarantee that we process each 2k character segment once and only once.

The ensuring inner segment in each loop iteration should swap each pair of elements from both ends towards the center until they meet or pass by each other. This will result in reversing the k string segment. Different languages have their unique ways for this. While high-level languages like Python and JavaScript have built-in methods to perform swapping seamlessly, more static languages like C++, C# or Java demand a manual swapping.

The anaylsis of time complexity for all solutions is O(n), where n is the size of the string. Whichever language you pick, the approach remains the same where we focus on reversing parts of the string using a 2k step to navigate through the string characters.