Construct Smallest Number From DI String

medium greedy stack string

Problem

Given a pattern of length n made of 'I' (increasing) and 'D' (decreasing), build a string num of length n + 1 using digits '1'..'9' each at most once, where num[i] < num[i+1] when pattern[i] is 'I' and num[i] > num[i+1] when pattern[i] is 'D'. Return the lexicographically smallest valid num.

Inputpattern = "IIIDIDDD"

Output"123549876"

Increasing at indices 0,1,2,4 and decreasing at 3,5,6,7; this is the smallest such number.

Inputpattern = "DDD"

Output"4321"

Four positions, all decreasing, so the smallest run of consecutive digits is 4,3,2,1.

pattern (only I and D, length 1..8)

def smallest_number(pattern):
    n = len(pattern)
    result, stack = [], []
    for i in range(n + 1):
        stack.append(str(i + 1))
        if i == n or pattern[i] == 'I':
            while stack:
                result.append(stack.pop())
    return ''.join(result)

function smallestNumber(pattern) {
  const n = pattern.length;
  const result = [], stack = [];
  for (let i = 0; i <= n; i++) {
    stack.push(String(i + 1));
    if (i === n || pattern[i] === 'I') {
      while (stack.length) result.push(stack.pop());
    }
  }
  return result.join('');
}

String smallestNumber(String pattern) {
    int n = pattern.length();
    StringBuilder result = new StringBuilder();
    Deque<Character> stack = new ArrayDeque<>();
    for (int i = 0; i <= n; i++) {
        stack.push((char) ('1' + i));
        if (i == n || pattern.charAt(i) == 'I') {
            while (!stack.isEmpty()) result.append(stack.pop());
        }
    }
    return result.toString();
}

string smallestNumber(string pattern) {
    int n = pattern.size();
    string result;
    stack<char> st;
    for (int i = 0; i <= n; i++) {
        st.push((char)('1' + i));
        if (i == n || pattern[i] == 'I') {
            while (!st.empty()) { result += st.top(); st.pop(); }
        }
    }
    return result;
}

Explanation

The output uses the digits 1..n+1 exactly once, so the question is only about their order. To make the number lexicographically smallest we want small digits as early as possible, while still honoring every 'I' and 'D'.

Process the positions left to right and keep a stack. At step i push the next unused digit i + 1. A 'D' means the next position must be smaller, so we hold the digit back on the stack to be placed later in descending order.

Whenever pattern[i] == 'I' (or we reach the last position), the upcoming relation is increasing, so the run of decreasing digits we were holding must be emitted now. We flush the whole stack, popping it onto the result — that reverses the held block into descending order, which is exactly what the 'D's require.

Because we always push the smallest still-available digit and only reverse a block when forced by a 'D' run, every flushed segment is the smallest it can be, giving the globally smallest string. The stack naturally handles consecutive 'D's of any length.

Example: pattern = "IDID". Pushing 1 then flushing on the 'I' gives "1"; pushing 2,3 and flushing on the next 'I' reverses to "32"; pushing 4,5 and flushing at the end reverses to "54". Concatenated: "13254".

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