Scale Engineer

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 <= 104
  • s consists of only lowercase English letters.
  • 1 <= k <= 104

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.

  1. 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.
  2. 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.
  3. 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.

class Solution {    public String reverseStr(String s, int k) {        StringBuilder result = new StringBuilder();        int i = 0;        int n = s.length();        while (i < n) {            int reverseEnd = Math.min(i + k, n);            StringBuilder reversedPart = new StringBuilder(s.substring(i, reverseEnd));            result.append(reversedPart.reverse());             if (reverseEnd < n) {                int nonReverseEnd = Math.min(i + 2 * k, n);                result.append(s.substring(reverseEnd, nonReverseEnd));            }                        i += 2 * k;        }        return result.toString();    }}

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.

Solutions

class Solution {public  String reverseStr(String s, int k) {    char[] chars = s.toCharArray();    for (int i = 0; i < chars.length; i += (k << 1)) {      for (int st = i, ed = Math.min(chars.length - 1, i + k - 1); st < ed;           ++st, --ed) {        char t = chars[st];        chars[st] = chars[ed];        chars[ed] = t;      }    }    return new String(chars);  }}

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 →

Next problem