2375. Construct Smallest Number From DI String

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.

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'.

Solution:

class Solution {
    public String smallestNumber(String pattern) {
        Deque<Integer> stack = new ArrayDeque<Integer>();

        StringBuilder sb = new StringBuilder();

        for (int i = 1; i <= pattern.length(); i++){
            stack.offerLast(i);
            if (pattern.charAt(i - 1) == 'I'){
                while(!stack.isEmpty()){
                    sb.append(stack.pollLast());
                }
            }
        }

        sb.append(pattern.length() + 1);

        while(!stack.isEmpty()){
            sb.append(stack.pollLast());
        }

        return sb.toString();
    }
}

The stack helps reverse the sequence whenever 'D' is encountered, ensuring numbers are added in a decreasing order.

Whenever 'I' is found, the stack is emptied to form the lexicographically smallest sequence possible up to that point.

class Solution {
    public String smallestNumber(String pattern) {
        Stack<Integer> stack = new Stack<Integer>();
       // 6 7 8

        StringBuilder sb = new StringBuilder();
        // sb =123549 8 76
        //  I I I D I D D D
        //                 i-1
        // 
        for (int i = 1; i < pattern.length() + 1; i++){
            stack.push(i); // 1 //2 
            if (pattern.charAt(i - 1) == 'I'){
                while(!stack.isEmpty()){
                    sb.append(stack.pop());
                }
            }
        }

        sb.append(pattern.length() + 1); // 8 + 1
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }

        return sb.toString();
    }
}

1. Understand the Problem Clearly

The goal is to generate the smallest possible number that satisfies the given pattern of 'I' (increasing) and 'D' (decreasing) using digits from 1 to n + 1 where n is the length of the pattern. The output should be lexicographically smallest.

2. Analyze and Identify Key Observations

• Patterns: 'I' means we want the current number to be smaller than the next one, and 'D' means it should be larger.
• Use a Stack: Whenever 'D' appears, it signifies that multiple numbers need to be added in decreasing order.

3. Decide on a Suitable Data Structure

• A stack (Deque) is appropriate because it allows reversing the order of the elements whenever a 'D' is encountered, helping to maintain the smallest lexicographical sequence.

4. Plan the Solution:

• Initialize an empty stack to hold numbers temporarily.
• Traverse through each character of the pattern while iterating over the sequence 1 to n + 1.
• Push the current digit into the stack.
• Whenever 'I' is encountered, pop all elements from the stack and append them to the result.
• After completing the loop, append any remaining elements in the stack to ensure all 'D' cases are handled.

5. Code the Solution

Implement the solution efficiently with time complexity O(n) since each element is pushed and popped from the stack at most once.

6. Analyze the Solution

• Time Complexity: O(n) because each digit is processed exactly once.
• Space Complexity: O(n)due to the use of the stack.

7. Edge Cases to Consider

• Single character patterns: 'I' or 'D'.
• Patterns with only 'I's or only 'D's.
• Ensure that the function handles empty or invalid input gracefully.

My Thought Process During the Interview:

• I would communicate my understanding of the problem and confirm it with the interviewer.
• I would discuss the choice of data structure and why a stack is appropriate.
• I'd write the code step-by-step, explaining each line.
• Finally, I would analyze the complexity and test the solution with various patterns to demonstrate correctness.