Reverse the First k of Every 2k

easy Strings

Cut the word into blocks of 2k letters from the left. In every block, reverse the first k letters and keep the next k as they are. If the last block has fewer than k letters, reverse all of them. If it has k to 2k - 1 letters, reverse only the first k. Input is the word and then k, separated by a space.

Constraints

1 <= length <= 10^4
1 <= k <= 10^4

Examples

Input

abcdefg 2

Output

bacdfeg

string-chunks
two-pointers

Solutions

Best approachTime O(n)Space O(n)

We jump 2k letters at a time. Inside each jump we swap the two ends of the first k letters until they meet. O(n) time.

Same code works in Java810172125Basic features only, so nothing changes between versions.

/*
 * Problem : Reverse in blocks.
 * Input   : The word and k.
 * Output  : The new word.
 * Approach: Swap in place.
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static String solve(String a, String b) {
        // Step 1: The second word is the number k.
        int k = Integer.parseInt(b);
        char[] letters = a.toCharArray();
        // Step 2: Visit the start of every 2k block. Reverse the first k letters (or fewer at the end) with two ends moving inward.
        for (int start = 0; start < letters.length; start += 2 * k) {
            int left = start;
            int right = Math.min(start + k, letters.length) - 1;
            while (left < right) {
                char temp = letters[left];
                letters[left++] = letters[right];
                letters[right--] = temp;
            }
        }
        return new String(letters);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String a = scanner.next();
        String b = scanner.next();
        System.out.println(solve(a, b));
    }
}

Hints (2)

What is the right end when fewer than k letters are left?
How far is the next block start?