Construct Smallest Number From DI String

Problem Description

You are given a 0-indexed string pattern of length n consisting of the characters 'I' meaning increasing and 'D' meaning decreasing. A 0-indexed string num of length n + 1 is created using the following conditions:

• num consists of the digits '1' to '9', where each digit is used at most once.
• If pattern[i] == 'I', then num[i] < num[i + 1].
• If pattern[i] == 'D', then num[i] > num[i + 1]. Return the lexicographically smallest possible string num that meets the conditions.

Key Insights

• The digits from '1' to '9' must be used without repetition.
• The pattern provides a structure that defines how the digits should be arranged.
• A greedy approach can be employed to build the smallest number by considering segments defined by 'D's and 'I's.
• When encountering 'D's, we need to reverse the order of the digits to satisfy the decreasing condition.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a greedy approach. We will iterate through the pattern and keep track of the segments of increasing and decreasing patterns. For each segment, we will generate the smallest possible digits in the required order. We can utilize a stack to manage the digits efficiently, especially for the decreasing segments where we need to reverse the order.

1. Initialize an empty list (or stack) to hold the digits.
2. Iterate through the pattern, and for each character:
   • If the character is 'I', add the current digit to the stack and then pop all elements from the stack to the result (to maintain the increasing order).
   • If the character is 'D', just add the current digit to the stack.
3. After processing all characters in the pattern, we need to add the last digit and pop any remaining elements in the stack to the result.
4. Convert the result list to a string and return it.

Code Solutions