# Solution by kevin.white.bcn

• #### Approach #1 O(n/k) complexity

Intuition

Only examine the first k characters of each 2k group of characters.

Algorithm

s = "abcdefg"
k = 2

Our objective is to output "bacdfeg". We immediatly observe that characters "cdg" do not change. This leads to the intuition that we need only examine the first k characters of each 2k group:

``````// s = "abcdefg", s.Length = 7, k = 2
for(int n = 0; n < s.Length; n+=2*k) {
// values of n are [0,4] = 2 iterations
}
``````

Now we have a method of iterating each 2k group, we now need to reverse the first k characters of each group. Gotcha: do not iterate beyond the length of s. So, we need to now iterate from n to n + k or s.Length, whichever is smaller!

``````int m = Math.Min(n + k, s.Length);

for(int j = n; j < m; j++) {
// Remaining algorithm
}

``````

The outer-loop iterates each 2k group, the inner-loop the first k characters of each 2k group. Now we simply reverse the characters.

``````// Calculate relative position in group e.g. first-char has pos 0, second-char pos 1, ...
int pos = j - n;

// Calculate the new position to reverse the string (i.e. place characters beginning from the end)
int newPos = m - pos - 1;

// Simply set the character in the output string
a[newPos] = s[j];
``````

A table helps visualise the logic:

n m = (Math.min(n+k, s.Length)) j pos = (j - n) newPos = (m - pos - 1)
0 2 0 0 1
0 2 1 1 0
4 6 4 0 5
4 6 5 1 4

We can see from the above table that the character at j is being moved to the correct new position (newPos). Producing a table like the above with a few different inputs was key to solving the problem.

C#

``````public class Solution {
// Catch error conditions
if (string.IsNullOrEmpty(s) || k < 2) return s;

char[] a = s.ToCharArray();

// Outer-loop moves nt ot he beginning of each 2k group
for(int n = 0; n < s.Length; n += 2*k)
{
// Determine where the current reverse should end: either (a) after transversing k characters or (b) coming to the end of the string (whichever is smaller)
int m = Math.Min(n + k, s.Length);

// Inner-loop performs the actual reversing of the characters
for(int j = n; j < m; j++)
{
// Calculate position of character within group e.g. first character is pos 0, second pos 1 ...
int pos = j - n;

// Calculate the position of the new character, which is simply at the end of the group - pos
int newPos = m - pos - 1;

// Place the character in the new position
a[newPos] = s[j];
}
}

return new string(a);
}
``````

Complexity Analysis

• Time complexity : \$\$O(n/k)\$\$
NOTE: this is an approximation but a good fit.
• Space complexity : \$\$O(1)\$\$

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.