# LeetCode 942: DI String Match

## Problem Restatement

We are given a string `s` of length `n`.

Each character is either:

```python
"I"
```

or:

```python
"D"
```

We need to return any permutation `perm` of the integers from `0` to `n` such that:

| Character | Required relation |
|---|---|
| `s[i] == "I"` | `perm[i] < perm[i + 1]` |
| `s[i] == "D"` | `perm[i] > perm[i + 1]` |

If multiple answers exist, any valid answer is accepted. The official statement defines the same reconstruction task for a permutation of `[0, n]`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `s` containing only `"I"` and `"D"` |
| Output | A permutation of integers from `0` to `len(s)` |
| Length | Output length is `len(s) + 1` |
| Valid answer | Any permutation satisfying all relations |

Function shape:

```python
class Solution:
    def diStringMatch(self, s: str) -> list[int]:
        ...
```

## Examples

Example 1:

```python
s = "IDID"
```

One valid answer is:

```python
[0, 4, 1, 3, 2]
```

Check each relation:

| Index | Character | Check |
|---:|---|---|
| 0 | `I` | `0 < 4` |
| 1 | `D` | `4 > 1` |
| 2 | `I` | `1 < 3` |
| 3 | `D` | `3 > 2` |

Example 2:

```python
s = "III"
```

A valid answer is:

```python
[0, 1, 2, 3]
```

Every adjacent pair increases.

Example 3:

```python
s = "DDI"
```

A valid answer is:

```python
[3, 2, 0, 1]
```

The first two relations decrease, and the last relation increases.

These examples match the official examples.

## First Thought: Try Permutations

A direct method is to generate every permutation of:

```python
[0, 1, 2, ..., n]
```

Then test whether it satisfies the pattern.

This is not practical.

There are `(n + 1)!` permutations, while `n` can be up to `10^5`. We need to construct a valid answer directly.

## Key Insight

Use the smallest and largest remaining numbers.

Keep two pointers:

| Pointer | Meaning |
|---|---|
| `low` | Smallest unused number |
| `high` | Largest unused number |

When we see `"I"`, we need the current value to be smaller than the next value.

So we can safely place the smallest remaining number.

When we see `"D"`, we need the current value to be larger than the next value.

So we can safely place the largest remaining number.

This works because choosing an extreme value guarantees that the next value can satisfy the relation.

## Algorithm

Initialize:

```python
low = 0
high = len(s)
ans = []
```

For each character `c` in `s`:

If `c == "I"`:

```python
ans.append(low)
low += 1
```

If `c == "D"`:

```python
ans.append(high)
high -= 1
```

After processing all characters, exactly one number remains.

Append it:

```python
ans.append(low)
```

Return `ans`.

## Walkthrough

Use:

```python
s = "IDID"
```

Start:

```python
low = 0
high = 4
ans = []
```

| Character | Action | `ans` | Remaining range |
|---|---|---|---|
| `I` | append `low = 0` | `[0]` | `1..4` |
| `D` | append `high = 4` | `[0, 4]` | `1..3` |
| `I` | append `low = 1` | `[0, 4, 1]` | `2..3` |
| `D` | append `high = 3` | `[0, 4, 1, 3]` | `2..2` |

Append the last remaining value:

```python
[0, 4, 1, 3, 2]
```

This satisfies `"IDID"`.

## Correctness

The algorithm always uses each number at most once because it only takes from the current unused range `[low, high]`, then moves one boundary inward.

When the current character is `"I"`, the algorithm appends `low`, the smallest unused number. The next number must come from the remaining range, where every value is greater than `low`. Therefore, the required relation `perm[i] < perm[i + 1]` can be satisfied.

When the current character is `"D"`, the algorithm appends `high`, the largest unused number. The next number must come from the remaining range, where every value is smaller than `high`. Therefore, the required relation `perm[i] > perm[i + 1]` can be satisfied.

After processing all `n` characters, one unused number remains. Appending it completes a permutation of all integers from `0` to `n`.

Each relation was made valid at the moment its left value was chosen, so the final array satisfies every character in `s`.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We process each character once |
| Space | `O(n)` | The output array has length `n + 1` |

## Implementation

```python
class Solution:
    def diStringMatch(self, s: str) -> list[int]:
        low = 0
        high = len(s)
        ans = []

        for c in s:
            if c == "I":
                ans.append(low)
                low += 1
            else:
                ans.append(high)
                high -= 1

        ans.append(low)
        return ans
```

## Code Explanation

`low` starts as the smallest available number:

```python
low = 0
```

`high` starts as the largest available number:

```python
high = len(s)
```

For an increasing relation, use the smallest available value:

```python
if c == "I":
    ans.append(low)
    low += 1
```

For a decreasing relation, use the largest available value:

```python
else:
    ans.append(high)
    high -= 1
```

At the end, `low == high`, so either value is the last remaining number:

```python
ans.append(low)
```

## Testing

```python
def is_valid(s, perm):
    n = len(s)

    if sorted(perm) != list(range(n + 1)):
        return False

    for i, c in enumerate(s):
        if c == "I" and not (perm[i] < perm[i + 1]):
            return False

        if c == "D" and not (perm[i] > perm[i + 1]):
            return False

    return True

def run_tests():
    sol = Solution()

    ans = sol.diStringMatch("IDID")
    assert is_valid("IDID", ans)

    ans = sol.diStringMatch("III")
    assert is_valid("III", ans)

    ans = sol.diStringMatch("DDI")
    assert is_valid("DDI", ans)

    ans = sol.diStringMatch("I")
    assert is_valid("I", ans)

    ans = sol.diStringMatch("D")
    assert is_valid("D", ans)

    ans = sol.diStringMatch("DIDDI")
    assert is_valid("DIDDI", ans)

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `"IDID"` | Alternating pattern |
| `"III"` | Strictly increasing |
| `"DDI"` | Standard decreasing then increasing |
| `"I"` | Smallest increasing case |
| `"D"` | Smallest decreasing case |
| `"DIDDI"` | Mixed pattern |