Approach #1: Direct [Accepted]
Intuition and Algorithm
We will reverse each block of
2k characters directly.
Each block starts at a multiple of
2k: for example,
0, 2k, 4k, 6k, .... One thing to be careful about is we may not reverse each block if there aren't enough characters.
To reverse a block of characters from
j, we can swap characters in positions
Time Complexity: , where is the size of
s. We build a helper array, plus reverse about half the characters in
Space Complexity: , the size of
Analysis written by: @awice.