# Write a program to match decrement increment string

## The problem:

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],
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 = "IIDII"
Output: [0, 1, 5, 2, 3, 4]
```

## The algorithm:

```
Suppose S.length = 4 and S="IDID", so the numbers we need to fill in the result set is 0 1 2 3 4
if the current char is 'I', we want to pick a number in the current potential options (0-4) that satisfies all scenarios in the next loop, it should be the smallest one, which is 0
now the rest of the options are 1 2 3 4
if the current char is 'D', again, we want to make sure that FOR EVERY NUMBER WE PICK IN NEXT ROUND will satisfy a[current] > a[current+1], then pick the largest value in 1 2 3 4, which is 4
then set becomes [1 2 3], we repeat the above
the thinking is really similar to "greedy" that we pick some number that can most satisfy the cases for the next loop.
For simulating the above logic we saw above. We have to keep track of the ends of both.
Implementation: Keeping track of both ends can be implemented in two ways,
1. Using a Two pointer algorithm to keep track of ends. Keep l and r variables...
2. Use a Deque to keep track of the ends

```

## The solution:

```const diStringMatch = (str) => {
const output = [];
let increment = 0;
let decrement = str.length;
for (let i = 0; i < str.length + 1; i ++) {
(str[i] === 'I') ? output.push(increment++) : output.push(decrement--);
}
return output;
}
console.log(diStringMatch('IIDII'));
```