Reverse String II

Easy

#0525Time: O(N), where N is the length of the string. We iterate through the string once. Operations inside the loop like `substring`, `StringBuilder` creation, and `reverse` take time proportional to `k`. The total time is the sum over all blocks, which is linear in N.Space: O(N). A `StringBuilder` of size N is used to build the result. Additionally, temporary substrings and `StringBuilder` objects of size up to `k` are created in each iteration, contributing to the overall space usage.

Patterns

Two Pointers

Data structures

String

Prompt

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 other as original.

Example 1:

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

Example 2:

Input: s = "abcd", k = 2
Output: "bacd"

Constraints:

1 <= s.length <= 10⁴
s consists of only lowercase English letters.
1 <= k <= 10⁴

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We iterate through the string, building a new reversed string piece by piece using a StringBuilder. For every 2k characters, we take the first k, reverse them, and append them to our result, followed by the next k characters which are appended without modification.

Algorithm

Initialize an empty StringBuilder called result.
Initialize an index i = 0.
Loop while i is less than the length of the string s:
- Calculate the end index j of the part to be reversed: j = min(i + k, s.length()).
- Extract the substring from i to j.
- Reverse this substring and append it to result.
- Calculate the end index l of the current 2k block: l = min(i + 2k, s.length()).
- If j < l, append the substring from j to l to result.
- Increment i by 2k.
Return result.toString().

Walkthrough

We initialize a StringBuilder to construct the final string. The logic iterates through the input string s with a step size of 2k. In each step, we handle a block of up to 2k characters.

Identify and Reverse: We first determine the segment to be reversed. This segment starts at the current index i and ends at min(i + k, s.length()). This min function correctly handles the case where fewer than k characters are left. We extract this substring, reverse it using a temporary StringBuilder, and append it to our main result StringBuilder.
Append Unchanged Part: Next, we identify the second part of the block, which should not be reversed. This segment starts where the first one ended and goes up to min(i + 2k, s.length()). We extract this substring and append it directly to the result.
Iteration: We then advance our main index i by 2k to move to the next block.

After the loop has processed the entire string, we convert the StringBuilder to a string and return it.

1class Solution {2    public String reverseStr(String s, int k) {3        StringBuilder result = new StringBuilder();4        int i = 0;5        int n = s.length();6        while (i < n) {7            int reverseEnd = Math.min(i + k, n);8            StringBuilder reversedPart = new StringBuilder(s.substring(i, reverseEnd));9            result.append(reversedPart.reverse());10 11            if (reverseEnd < n) {12                int nonReverseEnd = Math.min(i + 2 * k, n);13                result.append(s.substring(reverseEnd, nonReverseEnd));14            }15            16            i += 2 * k;17        }18        return result.toString();19    }20}

Complexity

Time

O(N), where N is the length of the string. We iterate through the string once. Operations inside the loop like `substring`, `StringBuilder` creation, and `reverse` take time proportional to `k`. The total time is the sum over all blocks, which is linear in N.

Space

O(N). A `StringBuilder` of size N is used to build the result. Additionally, temporary substrings and `StringBuilder` objects of size up to `k` are created in each iteration, contributing to the overall space usage.

Trade-offs

Pros

Conceptually straightforward, directly translating the problem statement into code.
Relatively easy to implement without complex data structures.

Cons

Less efficient due to the creation of multiple temporary string and StringBuilder objects within the loop. This can lead to higher memory overhead and performance degradation from frequent garbage collection.

A more optimized approach involves converting the string to a character array to perform the reversals in-place. This avoids the overhead of creating new string objects repeatedly. We iterate through the array in steps of 2k and reverse the required segments directly within the array using a two-pointer technique.

Algorithm

Convert the input string s to a character array a.
Iterate through the array with an index start from 0 to a.length - 1, with a step of 2 * k.
In each iteration, determine the left and right boundaries of the segment to reverse:
- left = start
- right = min(start + k - 1, a.length - 1)
Call a helper function reverse(a, left, right).
The reverse function swaps elements from the ends towards the center using two pointers until they meet.
After the loop, create a new string from the modified character array a and return it.

Walkthrough

Since strings are immutable in Java, we first convert the input string s into a character array a. This allows us to modify characters directly.

The main logic iterates through this array with a start index, which is incremented by 2k in each step. This start index marks the beginning of each block to be processed.

For each block, we need to reverse the first k characters. The indices for this reversal are from start to min(start + k - 1, a.length - 1). The min function is key to correctly handling the final part of the string, which might be shorter than k or 2k.

A helper function, reverse(char[] a, int left, int right), performs the in-place reversal. It uses two pointers, left and right, initialized to the start and end of the segment. It swaps the characters at these pointers and moves them towards each other until they cross.

After the loop finishes, the character array a contains the desired arrangement. We then construct a new string from this array and return it.

1class Solution {2    public String reverseStr(String s, int k) {3        char[] a = s.toCharArray();4        for (int start = 0; start < a.length; start += 2 * k) {5            int i = start;6            int j = Math.min(start + k - 1, a.length - 1);7            reverse(a, i, j);8        }9        return new String(a);10    }11 12    private void reverse(char[] a, int i, int j) {13        while (i < j) {14            char temp = a[i];15            a[i] = a[j];16            a[j] = temp;17            i++;18            j--;19        }20    }21}

Complexity

Time

O(N), where N is the length of the string. We traverse the array once. Each character is visited a constant number of times (once in the main loop, and at most once during a reversal swap). This results in a linear time complexity.

Space

O(N). In Java, this approach requires `O(N)` space to store the character array, as strings are immutable. In languages with mutable strings, this could be an `O(1)` space solution (excluding input storage).

Trade-offs

Pros

More efficient in terms of both time and memory as it avoids creating numerous temporary objects.
Modifies data in-place (on the character array), which is an efficient and common programming pattern.

Cons

Requires an initial O(N) space overhead to convert the immutable string to a mutable character array in Java.

Solutions

Solution

1class Solution {2public3  String reverseStr(String s, int k) {4    char[] chars = s.toCharArray();5    for (int i = 0; i < chars.length; i += (k << 1)) {6      for (int st = i, ed = Math.min(chars.length - 1, i + k - 1); st < ed;7           ++st, --ed) {8        char t = chars[st];9        chars[st] = chars[ed];10        chars[ed] = t;11      }12    }13    return new String(chars);14  }15}

1class Solution {2public:3  string reverseStr(string s, int k) {4    for (int i = 0, n = s.size(); i < n; i += (k << 1)) {5      reverse(s.begin() + i, s.begin() + min(i + k, n));6    }7    return s;8  }9};

1''' class range(start, stop, step=1) >>> k = 1 >>> for i in range(0, 9, k): ... print(i) ... 0 1 2 3 4 5 6 7 8 >>> for i in range(0, 9, k << 1): ... print(i) ... 0 2 4 6 8 ''' ''' reversed(t[i : i + k]) VS t[i : i + k][::-1] reversed(t[i : i + k]) returns an iterator that yields elements of the sequence in reverse order more suitable when you don't need a list or are performing operations that can take advantage of an iterator like join() t[i : i + k][::-1] slicing to create a new list that is a reversed version of the slice t[i : i + k] more convenient where you need the reversed sublist to be a list >>> t = [11,22,33,44,55] >>> >>> >>> t[1:3][::-1] [33, 22] >>> >>> reversed(t[1:3]) <list_reverseiterator object at 0x109022950> >>> >>> list(reversed(t[1:3])) [33, 22] ''' class Solution : def reverseStr ( self , s : str , k : int ) -> str : t = list ( s ) for i in range ( 0 , len ( t ), k << 1 ): # protected from out-of-index error t [ i : i + k ] = reversed ( t [ i : i + k ]) return '' . join ( t ) ############ class Solution ( object ): def reverseStr ( self , s , k ): """ :type s: str :type k: int :rtype: str """ cnt = 0 isFirst = True a = "" b = "" ans = [] for c in s : if isFirst : a = c + a else : b += c cnt += 1 if cnt == k : if isFirst : ans . append ( a ) a = "" else : ans . append ( b ) b = "" isFirst = not isFirst cnt = 0 return "" . join ( ans ) + a + b

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem