## Algorithm

Problem Name: 942. 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'`.

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int[] diStringMatch(String S) {
int n = S.length();
int low = 0;
int high = n;
int[] ans = new int[n + 1];
for (int i = 0; i < n; i++) {
ans[i] = S.charAt(i) == 'I' ? low++ : high--;
}
ans[n] = low;
return ans;
}
}
``````
Copy The Code &

Input

cmd
s = "IDID"

Output

cmd
[0,4,1,3,2]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const diStringMatch = function(S) {
const N = S.length
const arr = []
for(let i = 0; i <= N; i++) {
arr[i] = i
}
const res = []
for(let i = 0; i < N; i++) {
if(S[i] === 'I') {
res.push(arr.shift())
} else if(S[i] === 'D') {
res.push(arr.pop())
}
}
res.push(arr.pop())
return res
};
``````
Copy The Code &

Input

cmd
s = "IDID"

Output

cmd
[0,4,1,3,2]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def diStringMatch(self, S):
l, r, arr = 0, len(S), []
for s in S:
arr.append(l if s == "I" else r)
l, r = l + (s == "I"), r - (s == "D")
return arr + [l]
``````
Copy The Code &

Input

cmd
s = "III"

Output

cmd
[0,1,2,3]

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0942_DIStringMatch
{
public int[] DiStringMatch(string S)
{
var result = new int[S.Length + 1];
int lo = 0, hi = S.Length;
for (int i = 0; i < S.Length; i++)
{
if (S[i] == 'I') result[i] = lo++;
else if (S[i] == 'D') result[i] = hi--;
}

result[S.Length] = lo;
return result;
}
}
}
``````
Copy The Code &

Input

cmd
s = "III"

Output

cmd
[0,1,2,3]