541. Reverse String II

EasyTwo PointersString
Leetcode Link

Problem Description

The problem presents a string manipulation scenario where we are asked to modify the string in a specific pattern based on a parameter k. You are given the string s and an integer k. The task is to reverse every first k characters in each 2k segment of the string, starting from the beginning.

Here's the pattern we need to follow:

  • If a segment has 2k characters: reverse the first k characters and leave the next k characters in the original order.
  • If a segment has between k and 2k-1 characters: reverse the first k characters and leave the rest in the original order.
  • If a segment has fewer than k characters: reverse all of them.

It's important to note that reversing less than k characters happens only if those are the last characters in the string and their count is less than k.

Intuition

To solve this problem, we can iterate through the string in increments of 2k since we know that every 2k interval will require the same operation – reverse the first k characters. To implement this in code, we'll follow these steps:

  1. Convert the string s into a list of characters since strings in Python are immutable and we want to efficiently manipulate individual characters.

  2. Use a loop to work through the string in chunks of 2k. For each iteration, only pay attention to the current section of the string that is 2k in length. Within this current section, we only need to reverse the first k characters.

  3. When reversing, we'll use the slice notation in Python, t[i : i + k], where t is the list of characters from the original string, and i is the start of the current 2k segment. Reverse this slice and replace the original contents with the reversed ones.

  4. After the loop has processed the entire list, convert the list of characters back into a string using ''.join(t) and return the new string.

The provided solution takes advantage of list slicing and the reversed function in Python, which makes it a clean and efficient approach to solving the problem.

Learn more about Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Solution Approach

The provided solution uses several key programming concepts to solve the problem efficiently—list manipulation, slicing, looping, and in-place reversing of a sequence.

Here is how the solution is implemented:

  1. Convert the String to a List: Since strings in Python are immutable and cannot be changed in place, the first step is to convert the string s into a list of characters, t = list(s).

  2. Loop through the List in Chunks of 2k: The next step is to iterate over the list in chunks of 2k. This is achieved using a for loop with a range that starts at 0 and ends at the length of the list len(t), with step increments of 2k. In Python, k << 1 is a bitwise left shift operation that multiplies k by 2, giving us the required step size 2k.

  3. Reverse the First k Characters: For each chunk, reverse the first k characters. This is done by taking a slice t[i : i + k] from the current position i to the position i + k. The reversed() function is then used to reverse this slice. The reversed slice is then used to replace the original section of the list using slice assignment, which is an in-place operation.

  4. Join the List into a String: After the loop finishes, a new string is constructed from the list of characters using ''.join(t). This step converts the list with the modified characters back into a string.

  5. Return the Result: Finally, this new modified string is returned.

The algorithm relies on the efficiency of list operations and the ability to manipulate slices in Python to achieve the desired result without the need for additional data structures or complex patterns. By using the slice notation and reversed() function, the solution is concise and easy to read, while also minimizing the number of operations performed.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following shows the order of node visit in a Breadth-first Search?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Suppose we have the string s = "abcdefgh" and the value of k = 2. We are tasked to reverse every first k characters for each 2k segment of the string.

Following our solution approach:

  1. Convert the String to a List: We first convert the string into a list of characters t = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'].

  2. Loop through the List in Chunks of 2k: We will iterate over the list using steps of 2k = 4. Our loop will be over the indices 0, 4.

  3. Reverse the First k Characters: We reverse the first k characters for each segment:

    • At the first iteration (i=0), our first 2k segment is ['a', 'b', 'c', 'd']. The first k characters ['a', 'b'] are reversed to ['b', 'a']. The list now becomes t = ['b', 'a', 'c', 'd', 'e', 'f', 'g', 'h'].
    • At the second iteration (i=4), our second 2k segment is ['e', 'f', 'g', 'h']. The first k characters ['e', 'f'] are reversed to ['f', 'e']. The list now becomes t = ['b', 'a', 'c', 'd', 'f', 'e', 'g', 'h'].

  4. Join the List into a String: We join the list back into a string resulting in 'bacdfegh'.

  5. Return the Result: The final output we return will be the string "bacdfegh".

Each step of the solution works together to efficiently manipulate the sections of the string as required, ensuring that we only reverse what's needed and maintain the order of the rest of the characters.

Solution Implementation

1class Solution:
2    def reverseStr(self, s: str, k: int) -> str:
3        # Convert the input string to a list of characters for in-place modification.
4        chars = list(s)
5      
6        # Process the list in blocks of 2k characters.
7        for i in range(0, len(chars), 2*k):
8            # Reverse the first k characters in the current block.
9            # If the block is smaller than k, reverse the entire block.
10            chars[i : i + k] = reversed(chars[i : i + k])
11      
12        # Join the list of characters back into a string and return it.
13        return ''.join(chars)
14
15# The use of 'k << 1' in the original code is equivalent to '2*k'. 
16# Using '2*k' makes the intention clearer - to increment i by chunks of 2k.
17
1class Solution {
2    public String reverseStr(String s, int k) {
3        // Convert the input string 's' into a character array for in-place manipulation
4        char[] charArray = s.toCharArray();
5      
6        // Iterate over the array in blocks of size 2k
7        for (int startIndex = 0; startIndex < charArray.length; startIndex += (k * 2)) {
8            // Initialize 'endIndex' to the minimum of the last index of the block or the end of the array
9            int endIndex = Math.min(charArray.length - 1, startIndex + k - 1);
10          
11            // Reverse the characters in the current block from 'startIndex' to 'endIndex'
12            reverseCharacters(charArray, startIndex, endIndex);
13        }
14      
15        // Convert the reversed character array back to a string and return it
16        return new String(charArray);
17    }
18  
19    // Helper method to reverse a portion of the character array in place
20    private void reverseCharacters(char[] charArray, int startIndex, int endIndex) {
21        // Use two pointers to reverse the characters in the array
22        while (startIndex < endIndex) {
23            // Swap characters at 'startIndex' and 'endIndex'
24            char temp = charArray[startIndex];
25            charArray[startIndex] = charArray[endIndex];
26            charArray[endIndex] = temp;
27          
28            // Move the pointers closer to the middle of the array
29            startIndex++;
30            endIndex--;
31        }
32    }
33}
34
1class Solution {
2public:
3    string reverseStr(string str, int k) {
4        // Iterate over the string in chunks of 2k characters
5        for (int start = 0, len = str.size(); start < len; start += (k * 2)) {
6            // Calculate the end of the segment to be reversed, 
7            // which should not exceed the string's length
8            int end = min(start + k, len);
9
10            // Reverse the first k characters in the current 2k segment
11            // If the remaining characters are less than k, reverse all of them
12            reverse(str.begin() + start, str.begin() + end);
13        }
14        // Return the modified string
15        return str;
16    }
17};
18
1// Define the function to reverse every k characters of a string,
2// in each 2k interval.
3function reverseStr(str: string, k: number): string {
4    // Convert the string to an array of characters to manipulate
5    let arr = str.split('');
6
7    // Get the length of the string for later use
8    const len = arr.length;
9
10    // Iterate over the string in chunks of 2k characters
11    for (let start = 0; start < len; start += 2 * k) {
12        // Calculate the end index for the segment of the string that will be reversed,
13        // ensuring that it does not exceed the string's length
14        let end = Math.min(start + k, len) - 1;
15      
16        // Reverse the specified segment of the array using a two-pointer approach
17        for (let i = start, j = end; i < j; i++, j--) {
18            // Swap the characters at the i-th and j-th positions
19            let temp = arr[i];
20            arr[i] = arr[j];
21            arr[j] = temp;
22        }
23    }
24
25    // Return the modified string by joining the array back into a string
26    return arr.join('');
27}
28
29// Example usage:
30// reverseStr("abcdefg", 2) would return "bacdfeg"
31
Not Sure What to Study? Take the 2-min Quiz：

What's the relationship between a tree and a graph?

Time and Space Complexity

The time complexity of the given code can be broken down into two major operations: the loop that iterates over the string in chunks and the reversing of each chunk.

  • The loop iterates over the entire length of the string "s" with a step of "k << 1" which is equivalent to "2k" because the left-shift operator "<<" effectively multiplies the number by "2" for every shift. The loop thus runs approximately "len(s) / (2k)" times.

  • Inside each iteration, it reverses a sublist of "t" that is at most "k" elements long. The reverse operation takes "O(k)" time in the worst case.

Multiplying the number of iterations by the complexity of each iteration's operation gives us the total time complexity. Therefore, assuming "n" to be the length of the string "s", the overall time complexity of the code is approximately "O(n/k * k)" which simplifies to "O(n)".

The space complexity of the solution includes the additional space allocated for the conversion of the string "s" to a list "t". Since a list is created with the same number of elements as the input string, thus occupying "O(n)" space. No additional significant space is used that grows with the size of the input as the reversal is done in-place within the "t" list. Consequently, the space complexity of the code is "O(n)".

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫