A hiking trail is marked by n + 1 checkpoints, numbered 0 to n, connected by n consecutive segments. Segment i (for 0 <= i < n) runs from checkpoint i to checkpoint i+1 and is recorded as either U (the trail climbs, so checkpoint i+1 must sit at a higher rank than checkpoint i) or D (the trail descends, so checkpoint i+1 must sit at a lower rank than checkpoint i).
You must assign every checkpoint a distinct integer altitude rank from 0 to n (each value used exactly once) so that every segment's recorded direction is satisfied. Since more than one assignment can satisfy the directions, your output must be the one specific assignment produced by this rule: scan the segments from i = 0 to i = n - 1 while keeping two counters, low starting at 0 and high starting at n. For segment i: if it is U, assign checkpoint i the current value of low, then increase low by 1; if it is D, assign checkpoint i the current value of high, then decrease high by 1. After all n segments are processed, low and high are equal — assign that shared value to checkpoint n.
n.s of length n, consisting only of the characters U and D.Print n + 1 space-separated integers: the altitude ranks assigned to checkpoints 0 through n, in order.
1 <= n <= 10^4s consists only of the characters U and D.Example 1
Input
4 UDUD
Expected
0 4 1 3 2
Explanation
low=0, high=4. i=0 'U': assign low=0, low becomes 1. i=1 'D': assign high=4, high becomes 3. i=2 'U': assign low=1, low becomes 2. i=3 'D': assign high=3, high becomes 2. low and high are now both 2, so checkpoint 4 gets 2. The result is 0 4 1 3 2.
Example 2
Input
3 UUD
Expected
0 1 3 2
Explanation
low=0, high=3. i=0 'U': assign low=0, low becomes 1. i=1 'U': assign low=1, low becomes 2. i=2 'D': assign high=3, high becomes 2. low and high are now both 2, so checkpoint 3 gets 2. The result is 0 1 3 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →