Question

LeetCode Link | 541. Reverse String II | Easy

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.

Constrains

  • 1 <= s.length <= 10^4
  • s consists of only lowercase English letters.
  • 1 <= k <= 10^4

Examples

Example 1

Input: s = “abcdefg”, k = 2
Output: “bacdfeg”

Example 2

Input: s = “abcd”, k = 2
Output: “bacd”

Solution Approach

Method: Two-pointers

Constrains

  • None

This method does not have any limitations.

Concept Explanation

This question like the question 344. Reverse String that reverse the string, but with additional requirements that reverse only fist k characters for every 2k characters counting from the start of the string.

By doing that, we let index pointer i adds 2k each time of the loop, and reverse k length string like we did on 344. Reverse String.

The only edge case is when there are fewer than k characters left, which we only need to set the reverse string length to the end of the string to reverse all of them.

1
let right: number = Math.min(i + k - 1, arr.length);

Code

  • Time complexity: O(n)
  • Space complexity: O(1)

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function reverseStr(s: string, k: number): string {
    let arr: string[] = s.split('');
    // Jump index by 2k each time
    for (let i = 0; i < arr.length; i += 2 * k) {
        // reverse k length string
        let left: number = i;
        let right: number = Math.min(i + k - 1, arr.length);
        while(left < right) {
            [arr[left], arr[right]] = [arr[right], arr[left]];
            left++;
            right--;
        }
    }
    return arr.join('');
};

Conclusion

In this question, we use i += 2*k to break whole string into a smaller work string, and only consider revserse string in this smllar section without using any counter to count if we need to reverse or not. This solution logic can be applied on all other questions, try to break whole problem into a smllar chunk and only focus on this chunk which will cause less bugs in code.