# LeetCode 942. DI String Match

## Description

https://leetcode.com/problems/di-string-match/

A permutation `perm` of `n + 1` integers of all the integers in the range `[0, n]` can be represented as a string `s` of length `n` where:

• `s[i] == 'I'` if `perm[i] < perm[i + 1]`, and
• `s[i] == 'D'` if `perm[i] > perm[i + 1]`.

Given a string `s`, reconstruct the permutation `perm` and return it. If there are multiple valid permutations perm, return any of them.

Example 1:

```Input: s = "IDID"
Output: [0,4,1,3,2]
```

Example 2:

```Input: s = "III"
Output: [0,1,2,3]
```

Example 3:

```Input: s = "DDI"
Output: [3,2,0,1]
```

Constraints:

• `1 <= s.length <= 105`
• `s[i]` is either `'I'` or `'D'`.

## Explanation

Create the number list of S length + 1 integers. Iterate the string, if the character is ‘I’, pop the smallest number if the character is ‘D’, pop the biggest number.

## Python Solution

``````class Solution:
def diStringMatch(self, S: str) -> List[int]:
n = len(S)

numbers = [i for i in range(n + 1)]

results = []

for c in S:
if c == 'I':
results.append(numbers.pop(0))
elif c == 'D':
results.append(numbers.pop())

results.append(numbers.pop())

return results``````
• Time Complexity: O(N).
• Space Complexity: O(N).