#### 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)$$