LeetCode #2375 — MEDIUM

Construct Smallest Number From DI String

Move from brute-force thinking to an efficient approach using backtracking strategy.

The Problem

Problem Statement

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

Step 01

Brute Force Baseline

Problem summary: 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Backtracking · Stack · Greedy

Example 1

"IIIDIDDD"

Example 2

"DDD"

Core Insight

What unlocks the optimal approach

With the constraints, could we generate every possible string?
Yes we can. Now we just need to check if the string meets all the conditions.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Upper-end input sizes

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #2375: Construct Smallest Number From DI String
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;
            }
        }
    }
}

// Accepted solution for LeetCode #2375: Construct Smallest Number From DI String
func smallestNumber(pattern string) string {
	vis := make([]bool, 10)
	t := []byte{}
	ans := ""
	var dfs func(u int)
	dfs = func(u int) {
		if ans != "" {
			return
		}
		if u == len(pattern)+1 {
			ans = string(t)
			return
		}
		for i := 1; i < 10; i++ {
			if !vis[i] {
				if u > 0 && pattern[u-1] == 'I' && int(t[len(t)-1]-'0') >= i {
					continue
				}
				if u > 0 && pattern[u-1] == 'D' && int(t[len(t)-1]-'0') <= i {
					continue
				}
				vis[i] = true
				t = append(t, byte('0'+i))
				dfs(u + 1)
				vis[i] = false
				t = t[:len(t)-1]
			}
		}
	}
	dfs(0)
	return ans
}

# Accepted solution for LeetCode #2375: Construct Smallest Number From DI String
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

// Accepted solution for LeetCode #2375: Construct Smallest Number From DI String
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
    pub fn rust_example() {
        // Port the logic from the reference block below.
    }
}

// Reference (java):
// // Accepted solution for LeetCode #2375: Construct Smallest Number From DI String
// 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;
//             }
//         }
//     }
// }

// Accepted solution for LeetCode #2375: Construct Smallest Number From DI String
function smallestNumber(pattern: string): string {
    const n = pattern.length;
    const res = new Array(n + 1).fill('');
    const vis = new Array(n + 1).fill(false);
    const dfs = (i: number, num: number) => {
        if (i === n) {
            return;
        }

        if (vis[num]) {
            vis[num] = false;
            if (pattern[i] === 'I') {
                dfs(i - 1, num - 1);
            } else {
                dfs(i - 1, num + 1);
            }
            return;
        }

        vis[num] = true;
        res[i] = num;

        if (pattern[i] === 'I') {
            for (let j = res[i] + 1; j <= n + 1; j++) {
                if (!vis[j]) {
                    dfs(i + 1, j);
                    return;
                }
            }
            vis[num] = false;
            dfs(i, num - 1);
        } else {
            for (let j = res[i] - 1; j > 0; j--) {
                if (!vis[j]) {
                    dfs(i + 1, j);
                    return;
                }
            }
            vis[num] = false;
            dfs(i, num + 1);
        }
    };
    dfs(0, 1);
    for (let i = 1; i <= n + 1; i++) {
        if (!vis[i]) {
            res[n] = i;
            break;
        }
    }

    return res.join('');
}

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n!)

Space

O(n)

Approach Breakdown

EXHAUSTIVE

O(nⁿ) time

O(n) space

Generate every possible combination without any filtering. At each of n positions we choose from up to n options, giving nⁿ total candidates. Each candidate takes O(n) to validate. No pruning means we waste time on clearly invalid partial solutions.

BACKTRACKING + PRUNING

O(n!) time

O(n) space

Backtracking explores a decision tree, but prunes branches that violate constraints early. Worst case is still factorial or exponential, but pruning dramatically reduces the constant factor in practice. Space is the recursion depth (usually O(n) for n-level decisions).

Shortcut: Backtracking time = size of the pruned search tree. Focus on proving your pruning eliminates most branches.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Missing undo step on backtrack

Wrong move: Mutable state leaks between branches.

Usually fails on: Later branches inherit selections from earlier branches.

Fix: Always revert state changes immediately after recursive call.

Breaking monotonic invariant

Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.

Usually fails on: Indices point to blocked elements and outputs shift.

Fix: Pop while invariant is violated before pushing current element.

Using greedy without proof

Wrong move: Locally optimal choices may fail globally.

Usually fails on: Counterexamples appear on crafted input orderings.

Fix: Verify with exchange argument or monotonic objective before committing.