# Construct Smallest Number From DI String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/construct-smallest-number-from-di-string)
Canonical: https://scaleengineer.com/dsa/problems/construct-smallest-number-from-di-string
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** String, Stack
**Companies:** [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [josh technology](https://scaleengineer.com/companies/josh-technology)
---
## Problem
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'`.

# Approaches
## Brute-Force with Backtracking
This approach uses recursion and backtracking to explore all possible permutations of digits that could form a valid number. It systematically builds the number from left to right, trying all possible valid digits at each position. To ensure the result is lexicographically the smallest, digits are tried in increasing order ('1', '2', '3', ...). The first valid number of length `n+1` that is found is guaranteed to be the smallest possible one.
**Time:** O(k!) where k is the length of the output number (n+1). For the given constraints (n <= 8), this is at most O(9!), which is computationally expensive but feasible. · **Space:** O(n), where n is the length of the pattern. This is for the recursion stack depth and the `used` array.
**Pros:** Guarantees finding the correct, lexicographically smallest solution.; It's a general approach that can be adapted for many constraint satisfaction and permutation problems.
**Cons:** Very high time complexity, making it impractical for larger constraints.; The number of states can be very large, leading to a deep and wide recursion tree.
### Explanation
The core of this method is a backtracking function that constructs the output string `num` one digit at a time. We maintain a boolean array `used` to keep track of which digits from '1' to '9' have already been placed in `num`. The function attempts to fill the `k`-th position of `num`. It iterates through all unused digits `d` from '1' to '9'. For each `d`, it checks if placing it at `num[k]` would violate the condition imposed by `pattern[k-1]`. If `pattern[k-1]` is 'I', `d` must be greater than `num[k-1]`. If 'D', `d` must be smaller. If the condition is met, the function places `d` at `num[k]`, marks it as used, and recursively calls itself to fill the `(k+1)`-th position. If the recursion successfully builds a full-length number, we have found our answer. If not, it backtracks by undoing the choice of `d` and trying the next available digit.

```java
class Solution {
    String result = "";
    int n;

    public String smallestNumber(String pattern) {
        this.n = pattern.length();
        findSmallest("", new boolean[10]);
        return result;
    }

    private void findSmallest(String currentNum, boolean[] used) {
        if (!result.isEmpty()) {
            return; // Already found the smallest number, terminate early.
        }
        if (currentNum.length() == n + 1) {
            result = currentNum;
            return;
        }

        for (int i = 1; i <= 9; i++) {
            if (!used[i]) {
                if (currentNum.length() > 0) {
                    char lastChar = currentNum.charAt(currentNum.length() - 1);
                    char p = pattern.charAt(currentNum.length() - 1);
                    if (p == 'I' && (lastChar - '0') >= i) {
                        continue;
                    }
                    if (p == 'D' && (lastChar - '0') <= i) {
                        continue;
                    }
                }
                
                used[i] = true;
                findSmallest(currentNum + i, used);
                // If a result is found, we don't need to backtrack further from this path
                if (!result.isEmpty()) {
                    return;
                }
                used[i] = false; // Backtrack
            }
        }
    }
}
```
### Algorithm
- Define a recursive function, say `findSmallest(currentNum, usedDigits)`, to build the number.
- `currentNum` is the string built so far, and `usedDigits` is a boolean array to track used digits from '1' to '9'.
- The base case for the recursion is when `currentNum` reaches the required length (`n + 1`). Since we build the number by trying smaller digits first, the first complete number found will be the lexicographically smallest. We store it and stop further exploration.
- In the recursive step, iterate through digits `d` from '1' to '9'.
- If `d` has not been used, check if it can be appended to `currentNum` based on the last character of `currentNum` and the corresponding character in `pattern`.
- If the placement is valid, mark `d` as used and make a recursive call for the next position.
- After the recursive call, backtrack by un-marking `d` as used to explore other possibilities.

## Greedy Approach with a Stack
A highly efficient greedy approach can solve this problem in linear time. The strategy is to iterate through the digits `1, 2, ..., n+1` and use a stack to handle the formation of decreasing sequences. When we encounter an 'I', it signals that the preceding sequence of 'D's has ended. The numbers collected on the stack for this decreasing segment are then popped and appended to the result, which naturally reverses their order and satisfies the 'D' conditions.
**Time:** O(n), where n is the length of the pattern. Each number from 1 to `n+1` is pushed onto the stack once and popped from the stack once. · **Space:** O(n), where n is the length of the pattern. In the worst-case scenario (a pattern of all 'D's), the stack will store `n+1` elements.
**Pros:** Optimal time complexity of O(n).; Simple implementation using a standard stack data structure.; Single-pass solution.
**Cons:** The logic might be slightly less intuitive to grasp initially compared to a direct reversal approach.
### Explanation
We process the pattern from left to right. We use a counter to generate digits `1, 2, 3, ...`. For each position in the output number, we consider placing the next smallest available digit. These digits are pushed onto a stack. A character 'I' in the pattern (or the end of the pattern) acts as a trigger. It finalizes the preceding block of numbers. This block might have been governed by 'D's, requiring a decreasing sequence. By popping the numbers from the stack, we get them in reverse order of how they were pushed. Since we pushed `k, k+1, k+2, ...`, popping gives `..., k+2, k+1, k`, which is exactly the decreasing sequence needed. This ensures that for any segment, we use the smallest possible set of digits, and arrange them to be lexicographically minimal at the start of the segment.

```java
import java.util.Stack;

class Solution {
    public String smallestNumber(String pattern) {
        StringBuilder result = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        int n = pattern.length();

        for (int i = 0; i <= n; i++) {
            stack.push(i + 1);
            if (i == n || pattern.charAt(i) == 'I') {
                while (!stack.isEmpty()) {
                    result.append(stack.pop());
                }
            }
        }
        return result.toString();
    }
}
```
### Algorithm
- Initialize an empty result string (or `StringBuilder`) and an empty stack.
- Iterate with an index `i` from 0 to `n`, where `n` is the length of the pattern. This loop corresponds to the `n+1` digits of the output number.
- In each iteration, push the next available number, `i + 1`, onto the stack.
- If the current character `pattern[i]` is 'I', or if we have reached the end of the pattern (`i == n`), it marks the end of a decreasing sequence.
- At this point, pop all elements from the stack and append them to the result. This reverses the order of the numbers pushed for the segment, creating the required decreasing sequence.
- After the loop completes, the result string will hold the lexicographically smallest number.

## Greedy Approach with Reversal
This is another optimal greedy approach that is very intuitive. The idea is to start with the lexicographically smallest possible permutation of the required digits, which is simply the sorted sequence '123...'. This sequence satisfies all 'I' (increasing) conditions. Then, we iterate through the pattern and fix the segments that need to be decreasing ('D'). A block of consecutive 'D's implies a strictly decreasing subsequence of numbers. We achieve this by reversing the corresponding segment in our initial '123...' string.
**Time:** O(n), where n is the length of the pattern. The nested loops still result in linear time because each character of the pattern and each digit of the result is processed a constant number of times. · **Space:** O(n) to store the result string. The reversal is done in-place, so it requires O(1) auxiliary space.
**Pros:** Optimal O(n) time complexity.; The logic is very intuitive and easy to reason about.; Can be implemented with low overhead.
**Cons:** Requires a mutable string or character array to perform efficient in-place reversals.
### Explanation
Let the length of the pattern be `n`. The result will have length `n+1` and use digits from '1' to `n+1` to be lexicographically minimal. We start with a `StringBuilder` or `char[]` initialized to "123...(n+1)". We then scan the pattern. When we encounter a block of `k` consecutive 'D's starting at index `i`, it means `num[i] > num[i+1] > ... > num[i+k]`. In our initial string, this segment is `(i+1), (i+2), ..., (i+k+1)`. To satisfy the 'D's while keeping the numbers in this segment as small as possible, we must arrange these specific `k+1` numbers in decreasing order. This is achieved by simply reversing this segment of the string. We repeat this for every block of 'D's in the pattern.

```java
class Solution {
    public String smallestNumber(String pattern) {
        int n = pattern.length();
        StringBuilder res = new StringBuilder();
        for (int i = 0; i <= n; i++) {
            res.append((char)('1' + i));
        }

        for (int i = 0; i < n; i++) {
            if (pattern.charAt(i) == 'D') {
                int j = i;
                while (j < n && pattern.charAt(j) == 'D') {
                    j++;
                }
                reverse(res, i, j);
                i = j - 1;
            }
        }
        return res.toString();
    }

    private void reverse(StringBuilder sb, int start, int end) {
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
    }
}
```
### Algorithm
- First, create a candidate result string `res` consisting of digits '1' to `n+1` in increasing order (e.g., "1234" for a pattern of length 3).
- This initial string already satisfies all 'I' conditions.
- Iterate through the `pattern` string from left to right with an index `i`.
- If `pattern[i]` is an 'I', do nothing as the condition is already met.
- If `pattern[i]` is a 'D', it marks the start of a decreasing segment. Find the end of this contiguous block of 'D's. Let's say it ends at index `j-1`.
- Reverse the substring of `res` from index `i` to `j`.
- After reversing, update the loop counter `i` to `j-1` to continue scanning from the end of the processed 'D' block.
- The final `res` string is the answer.

# Solutions
### Java

```java
class Solution {
private
  boolean[] vis = new boolean[10];
private
  StringBuilder t = new StringBuilder();
private
  String p;
private
  String ans;
public
  String smallestNumber(String pattern) {
    p = pattern;
    dfs(0);
    return ans;
  }
private
  void dfs(int u) {
    if (ans != null) {
      return;
    }
    if (u == p.length() + 1) {
      ans = t.toString();
      return;
    }
    for (int i = 1; i < 10; ++i) {
      if (!vis[i]) {
        if (u > 0 && p.charAt(u - 1) == 'I' && t.charAt(u - 1) - '0' >= i) {
          continue;
        }
        if (u > 0 && p.charAt(u - 1) == 'D' && t.charAt(u - 1) - '0' <= i) {
          continue;
        }
        vis[i] = true;
        t.append(i);
        dfs(u + 1);
        t.deleteCharAt(t.length() - 1);
        vis[i] = false;
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  string ans = "";
  string pattern;
  vector<bool> vis;
  string t = "";
  string smallestNumber(string pattern) {
    this->pattern = pattern;
    vis.assign(10, false);
    dfs(0);
    return ans;
  }
  void dfs(int u) {
    if (ans != "")
      return;
    if (u == pattern.size() + 1) {
      ans = t;
      return;
    }
    for (int i = 1; i < 10; ++i) {
      if (!vis[i]) {
        if (u && pattern[u - 1] == 'I' && t.back() - '0' >= i)
          continue;
        if (u && pattern[u - 1] == 'D' && t.back() - '0' <= i)
          continue;
        vis[i] = true;
        t += to_string(i);
        dfs(u + 1);
        t.pop_back();
        vis[i] = false;
      }
    }
  }
};

```

### Python

```python
class Solution:
    def smallestNumber(self, pattern: str) -> str: def dfs(u): nonlocal ans if ans: return if u == len(pattern) + 1: ans = '' . join(t) return for i in range(1, 10): if not vis[i]: if u and pattern[u - 1] == 'I' and int(t[- 1]) >= i: continue if u and pattern[u - 1] == 'D' and int(t[- 1]) <= i: continue vis[i] = True t . append(str(i)) dfs(u + 1) vis[i] = False t . pop() vis = [False] * 10 t = [] ans = None dfs(0) return ans

```