652. The Smallest Arrangement Matching a Pattern
A pattern of n characters is given, each I or D. Build an arrangement of the numbers
0 to n such that, for every position i, the value RISES when the pattern has I and FALLS
when it has D.
Several arrangements usually work. Print the one that is SMALLEST when compared left to right.
IDID -> 0 2 1 4 3
III -> 0 1 2 3
DDI -> 2 1 0 3
## The construction that is NOT the answer
There is a well known one-pass method: keep lo = 0 and hi = n, take lo on an I and hi
on a D, then append whatever remains.
It produces a VALID arrangement and it is not the smallest. On IDID it gives 0 4 1 3 2,
while 0 2 1 4 3 is smaller and also valid.
That method is the usual answer to the usual version of this question, which does not ask for the smallest. Reading exactly what is wanted before reaching for a remembered construction is the point of putting this version here.
## Start sorted, then reverse each falling run
a = 0, 1, 2, ..., n
for each maximal run of D from i to j:
reverse a[i .. j]
A run of k consecutive D characters spans k + 1 positions, so the segment reversed runs
from the run's first index to one PAST its last.
## Why this is the smallest
Start from 0 1 2 ... n, which is the smallest arrangement of these values and already
satisfies every I.
Each maximal falling run must hold values in decreasing order, so the positions it covers must be a set of values arranged downwards. To keep the arrangement as small as possible, those positions should hold the SMALLEST values still available for them, which are exactly the ones already sitting there. Reversing puts that same set into the required decreasing order and changes nothing outside the run.
Since the runs are disjoint and separated by rising steps, the reversals do not interact.
## The reversal is where the two pointers are
Reversing a segment in place is the converging sweep: one pointer at each end, swap, step inward. It is the same three lines as the tail reversal in problem 625.
## Boundaries
A pattern of all I leaves the array untouched. A pattern of all D reverses the whole thing.
A single character gives 0 1 or 1 0.
## Cost
Time O(n). Space O(n) for the answer.
Constraints - `1 ≤ length of the pattern ≤ 200000` - the pattern contains only `I` and `D`
Input
One line containing the pattern, made only of the characters I and D.
Output
Print the n + 1 values on one line, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.