541.md

541. Reverse String II

Description

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less 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 left the other as original.

Example:

Input: s = "abcdefg", k = 2

Output: "bacdfeg"

Restrictions:The string consists of lower English letters only.Length of the given string and k will in the range [1, 10000]

Thinking Process

1. Iterate through the string 2k steps at a time
2. At each iteration, reverse the string from i to i + k -1 (or s.length() - 1 depending on if i + k - 1 overflow the length of the string)

Code

public class Solution {
    public String reverseStr(String s, int k) {
        char[] word = s.toCharArray();
        for(int i = 0; i < word.length; i += 2*k){
            reverse(word, i, i + k -1);
        }
        return new String(word);
    }
    
    void reverse(char[] word, int from, int to){
        to = to > word.length - 1 ? word.length - 1 : to;
        while(from < to){
            char temp = word[from];
            word[from++] = word[to];
            word[to--] = temp;
        }
    }
}

Complexity

1. Time complexity is O(n) as the string is scanned once
2. Space complexity is O(n)