Smallest Up-Down Sequence

Medium

A string pattern of length n made of the letters I and D describes how a sequence of n + 1 numbers moves: pattern[i] == 'I' means the next number is larger than the current one, and pattern[i] == 'D' means it is smaller. Arrange the numbers 1, 2, …, n + 1 (each exactly once) into a sequence that follows the pattern, and return the lexicographically smallest such sequence.

Example 1

pattern="IDD" → [1, 4, 3, 2]

The steps are up, down, down. Both [1, 4, 3, 2] and [2, 4, 3, 1] fit, and the first one is lexicographically smaller.

Example 2

pattern="DID" → [2, 1, 4, 3]

It starts with a drop: the smallest way is 2 then 1, then up to 4 and down to 3.

Example 3

pattern="II" → [1, 2, 3]

Constraints

1 ≤ len(pattern) ≤ 10⁵
pattern[i] is I or D

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Greedy Array String

Similar problems

Biggest Number From Pieces Medium Every Letter Once Medium Erase Digits for the Smallest Number Medium Ring of Flippable Words Medium Fix the Middle of the Line Medium

Input

pattern="IDD"

Expected

[1, 4, 3, 2]

Run checks the first 3 tests in your browser. Submit checks all 246 tests on the server, hidden ones included.