Smallest Number From a Comparison Pattern

You are given a string pattern of length n made up only of the characters 'I' and 'D'. Each character describes how two neighbouring digits of an answer string must compare:

• 'I' means the next digit is greater than the current one (increasing).
• 'D' means the next digit is less than the current one (decreasing).

Build a string num of length n + 1 such that:

• num uses only the digits '1' through '9', and each digit appears at most once.
• For every index i, if pattern[i] == 'I' then num[i] < num[i + 1], and if pattern[i] == 'D' then num[i] > num[i + 1].

Return the lexicographically smallest string num that satisfies these conditions.

Examples

Example 1

Input: pattern = "IIIDIDDD"
Output: "123549876"
Explanation:
At indices 0, 1, 2, and 4 the pattern is 'I', so num must increase there.
At indices 3, 5, 6, and 7 the pattern is 'D', so num must decrease there.
Other valid strings include "245639871" and "135749862", but "123549876"
is the smallest possible one.

Example 2

Input: pattern = "DDD"
Output: "4321"
Explanation:
Every step must decrease. Valid strings include "9876" and "7321", but
"4321" is the smallest four-digit string that strictly decreases.