# 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].

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'));