## Algorithm/Insights

The idea is to use the higher numbers for satisfying 'i' transitions and remaining numbers for 'd' transitions.

Let's look at an example. Say we have a string consisting of only 2 'i's and 3 'd's - 'ddidi'

Then out of numbers 1,2,3,4,5,6 we reserve two higher numbers 6 and 5 for 'i' transitions because no matter what the current number we can always satisfy 'i' transitions using these higher numbers. The number next to reserved numbers for 'i' transitions is put at the 0th position. In this case, number next to 6 and 5 would be 4 hence we make output[0] = 4. Note that out of 1,2,3,4,5,6 we have marked top 2 numbers that is 6 and 5 for 'i' transitions and next number to them that is 4 as a start value for output array - therefore remaining numbers(that is 3,2,1) would be used for 'd' transitions. Now we mark lowest number from the numbers reserved for 'i' transitions as increaseValue - in this case increaseValue would be 5. Similarly, we mark highest number from numbers that are going to used for 'd' transitions as decreaseValue - in this case decreaseValue would be 3.

Now the algorithm is very simple. Whenever we see a 'd' at string[i], we just put decreaseValue at output[i+1] and decrement decreaseValue by 1. And whenever we see a 'i' at string[i], we just put increaseValue at output[i+1] and increment increaseValue by 1. Output[0] is already initilaized to the number next to numbers reserved for 'i' and 'd' transitions.

In this case, for string 'ddidi' we will be using numbers 1,2,3,4,5,6

Numbers reserved for 'i' - 6,5

StartValue to be put at output[0] - 4

Numbers reserved for 'd' - 3,2,1

increaseValue marked at - 5

decreaseValue marked at - 3

output[0] = 4

output[1] = 3, decreaseValue updated to 2 (since 0th character for input is 'd')

output[2] = 2, decreaseValue updated to 1 (first character is 'd')

output[3] = 5, increaseValue updated to 6 (second character is 'i')

output[4] = 1, decreaseValue updated to 0 (third character is 'd')

output[5] = 6, increaseValue updated to 7 (fourth character is 'i')

Time taken by this algorithm is O(n).