Construct Smallest Number From DI String

Problem Statement

Given a pattern string indexed from zero consisting exclusively of letters 'I' (for "increasing") and 'D' (for "decreasing"), the challenge is to construct a numeric string num that is also zero-indexed and has a length of n + 1, where n is the length of the pattern. The characters in num are consecutive digits ranging from '1' to '9', used at most once per digit. The rules are straightforward: if an index i in the pattern contains 'I', the corresponding position in num must have a value less than the value at position i+1. Conversely, if an index i in the pattern contains 'D', the value at position i in num must be greater than the one at position i+1. The task is to determine the lexicographically smallest num that fits these rules.

Examples

Example 1

Input:

pattern = "IIIDIDDD"

Output:

"123549876"

Explanation:

At indices 0, 1, 2, and 4 we must have that num[i] < num[i+1].
At indices 3, 5, 6, and 7 we must have that num[i] > num[i+1].
Some possible values of num are "245639871", "135749862", and "123849765".
It can be proven that "123549876" is the smallest possible num that meets the conditions.
Note that "123414321" is not possible because the digit '1' is used more than once.

Example 2

Input:

pattern = "DDD"

Output:

"4321"

Explanation:

Some possible values of num are "9876", "7321", and "8742".
It can be proven that "4321" is the smallest possible num that meets the conditions.

Constraints

• 1 <= pattern.length <= 8
• pattern consists of only the letters 'I' and 'D'.

Approach and Intuition

The essence of this problem lies in determining a sequence of digits that strictly follow the increase or decrease rules dictated by each character in the pattern string, and ensuring that the resultant numeric string is the smallest in lexicographical order. Here's a structured approach to achieve this:

1. Identify and record the length of consecutive 'I's or 'D's in the pattern. This helps in understanding the required sequence of increasing or decreasing digits.
2. For a sequence of consecutive 'I's lasting k indices, you would ideally select the smallest k+1 available digits in increasing order. For example, if pattern has 'III', and considering smallest unused digits are from 1, the sequence would be 1234, where 1 is the smallest available digit and meets the pattern criteria.
3. For a sequence of consecutive 'D's lasting k indices, select the smallest k+1 digits but arrange them in decreasing order. If 'DDD' is the pattern portion, and considering the smallest unused digits from 4 (if 1, 2, and 3 were already used as per prior steps), using 654 would be ideal.
4. An important aspect is the transition between 'I' and 'D' or vice versa. If the pattern switches from 'I' to 'D', you'd need to ensure the last digit used in the increasing sequence is less than the first digit of the subsequent decreasing sequence.
5. With every digit choice, care must be taken to ensure the digit hasn't already been used, preserving the rule that each digit from '1' to '9' can be used at most once.
6. These steps help construct the sequence from left to right, continually adjusting as needed to adhere both to the 'I' and 'D' patterns and to ensure the smallest numerical value is achieved.

This logical, step-by-step strategy assures adherence to the constraints and patterns while also aiming for the lexicographical minimization of the string num.

Solutions

class Solution {
public:
    string minNumberFromString(string sequence) {
        int sequenceLen = sequence.size();
        int peak = 0, highest = 0, digit;
    
        vector<int> decrementSeq(sequenceLen + 1, 0);
    
        for (int i = sequenceLen - 1; i >= 0; --i) {
            if (sequence[i] == 'D')
                decrementSeq[i] = decrementSeq[i + 1] + 1;
        }
    
        string smallestNum = "";
    
        for (int idx = 0; idx <= sequenceLen; idx++) {
            if (sequence[idx] == 'I') {
                peak++;
                smallestNum += '0' + peak;
                peak = max(peak, highest);
                highest = 0;
            } else {
                digit = 1 + peak + decrementSeq[idx];
                smallestNum += '0' + digit;
                highest = max(highest, digit);
            }
        }
    
        return smallestNum;
    }
};