Reorder a String by Alternating Its Front and Back Characters
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Online Assessment
Given a string `s`, build a new string by taking characters alternately from the front and the back of `s`: the first character, then the last character, then the second character, then the second-to-last character, and so on, until every character of `s` has been used exactly once.
### Function Signature
```python
def reorder_front_back(s: str) -> str:
```
### Rules
- Let `n = len(s)`. The output is `s[0]`, `s[n-1]`, `s[1]`, `s[n-2]`, `s[2]`, `s[n-3]`, and so on, stopping as soon as `n` characters have been written.
- Every position of `s` is used exactly once, so the output also has length `n`. When `n` is odd, the middle character `s[n // 2]` is the last one written.
- Characters are copied unchanged.
### Constraints
- `1 <= len(s) <= 10^5`
- `s` consists of lowercase English letters.
### Examples
**Example 1**
```text
Input: s = "abcdef"
Output: "afbecd"
```
The characters are taken in the order `a` (first), `f` (last), `b` (second), `e` (second-to-last), `c`, `d`.
**Example 2**
```text
Input: s = "hello"
Output: "hoell"
```
The order is `h` (first), `o` (last), `e` (second), `l` (second-to-last), and finally the middle `l`.
**Example 3**
```text
Input: s = "x"
Output: "x"
```
Overview: Rearrange a string by taking characters alternately from its front and its back: first, last, second, second-to-last and so on until every character is used once. Tests clean index handling for even and odd lengths and building the result efficiently for long inputs.
Given a string `s` of lowercase English letters, build a new string by taking characters alternately from the front and the back of `s`: the first character, then the last character, then the second character, then the second-to-last character, and so on, until every character of `s` has been used exactly once.
Implement `reorder_front_back(s)` and return the new string.
### Rules
- Let `n = len(s)`. The output is `s[0]`, `s[n-1]`, `s[1]`, `s[n-2]`, `s[2]`, `s[n-3]`, and so on, stopping as soon as `n` characters have been written.
- Every position of `s` is used exactly once, so the output also has length `n`. When `n` is odd, the middle character `s[n // 2]` is the last one written.
- Characters are copied unchanged.
### Constraints
- `1 <= len(s) <= 10^5`
- `s` consists of lowercase English letters.
No value in this problem can exceed 2^31 - 1: the input and the output are both strings of length `n`.
### Examples
**Example 1**
```text
Input: s = "abcdef"
Output: "afbecd"
```
The characters are taken in the order `a` (first), `f` (last), `b` (second), `e` (second-to-last), `c`, `d`.
**Example 2**
```text
Input: s = "hello"
Output: "hoell"
```
The order is `h` (first), `o` (last), `e` (second), `l` (second-to-last), and finally the middle `l`.
Constraints
- 1 <= len(s) <= 10^5
- s consists of lowercase English letters.
Examples
Input: ('x',)
Expected Output: 'x'
Explanation: Singleton (n = 1): the only character is returned unchanged.
Input: ('ab',)
Expected Output: 'ab'
Explanation: Smallest even length: first then last, with no overlap.
Hints
- For a small string such as "hello", write down which index of s supplies each output character; the rules fix that index sequence completely.
- Think about how many positions remain unused at each end after every step. What should happen when exactly one unused position is left?
- The output has exactly len(s) characters, so check that no position is written twice or skipped, especially when the length is odd.