2375. Construct Smallest Number From DI String

Q: Is Construct Smallest Number From DI String easy or hard?

Construct Smallest Number From DI String is typically classified as a medium-level problem. The logic becomes straightforward once you recognize that consecutive 'D' segments must be reversed. Identifying the greedy stack strategy is the main challenge.

Q: Construct Smallest Number From DI String Python/Java solution

Most implementations follow the greedy stack pattern: iterate through the pattern, push the next digit, and pop the stack when encountering 'I'. This logic is easy to implement in Python, Java, C++, C, C#, or JavaScript because it only requires basic stack operations and string construction.

Q: How to solve Construct Smallest Number From DI String in O(n)?

Scan the pattern from left to right while assigning digits in increasing order. Use a stack to delay output for 'D' sequences, then pop when an 'I' appears to produce a decreasing segment. Because each digit is processed once, the total complexity stays linear at O(n).

Q: What is the best approach for Construct Smallest Number From DI String?

The greedy stack approach is the most widely used solution. Iterate through the DI pattern, push sequential digits onto a stack, and flush the stack whenever an 'I' appears or the pattern ends. This automatically reverses decreasing segments and produces the smallest valid number. The algorithm runs in O(n) time and O(n) space.

Q: Is Construct Smallest Number From DI String asked at Google/Amazon/Meta?

Greedy pattern construction problems like this frequently appear in interviews at large tech companies. Variants of DI pattern or stack-based sequence construction have been reported in interviews at companies such as Amazon and Google because they test greedy reasoning and stack usage.

Q: What data structure is used in Construct Smallest Number From DI String?

A stack is the primary data structure in the optimal solution. The stack temporarily stores digits until the algorithm determines where a decreasing segment ends, then pops elements to produce the correct order.

Q: What is the time complexity of Construct Smallest Number From DI String?

The optimal greedy solutions run in O(n) time, where n is the length of the DI string. Each digit is pushed and popped at most once when using the stack approach. Space complexity is O(n) for the stack or O(1) for the segment-reversal variant.

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

Approach overview

Problem Overview: You are given a string consisting of 'D' (decreasing) and 'I' (increasing). The goal is to build the smallest possible number using digits 1–9 without repetition such that the digits follow the pattern. For example, if the pattern contains D, the next digit must be smaller than the previous digit. The challenge is enforcing the pattern while keeping the overall number lexicographically smallest.

Approach 1: Greedy Approach with Stack (O(n) time, O(n) space)

This approach processes the pattern from left to right and uses a stack to temporarily store digits. Push numbers sequentially starting from 1. Whenever you encounter an 'I' or reach the end of the pattern, pop all elements from the stack and append them to the result. This reversal ensures that segments of 'D' automatically produce decreasing sequences while still using the smallest available digits. The key insight: delaying output until an increasing boundary lets you reverse the necessary portion to satisfy multiple consecutive D constraints.

This greedy strategy guarantees the smallest valid number because digits are assigned in increasing order and only reversed when the pattern forces a decrease. Each digit is pushed and popped once, making the algorithm linear. This is the most common interview solution and works well for patterns with long decreasing runs.

Approach 2: Construct from Left to Right (Greedy Pattern Handling) (O(n) time, O(1) extra space)

Another strategy builds the answer array directly while scanning the pattern. Start by filling the digits sequentially. When a 'D' segment appears, identify the full length of that decreasing run and reverse the corresponding portion of the result. For example, if the pattern contains DDD, the next four digits must form a decreasing sequence, so the digits assigned to that segment are reversed after placement.

This method relies on the same greedy observation: the smallest digits should appear as early as possible, but decreasing runs must be reversed to satisfy ordering constraints. Instead of using a stack, the algorithm manipulates segments directly. The logic stays simple and uses constant auxiliary memory.

Approach 3: Backtracking (O(9! ) worst case, O(n) space)

A brute-force method uses backtracking to generate permutations of digits 1–9 and check whether each permutation satisfies the DI pattern. Because the goal is the smallest valid number, the search can stop as soon as a valid candidate appears. While conceptually straightforward, the factorial search space makes this impractical for interviews. It mainly helps illustrate the constraint structure before applying a greedy optimization.

Recommended for interviews: The greedy stack solution is the expected answer. It demonstrates understanding of pattern constraints and efficient use of a greedy strategy with a stack. Explaining the brute-force backtracking approach first shows reasoning about the search space, but implementing the O(n) greedy method signals strong problem-solving skills.

Approach 1: Greedy Approach with Stack

This approach utilizes a stack to construct the number by handling 'I' and 'D' separately. For 'D', we keep adding digits to the stack and for 'I' we release them in reverse order which satisfies the 'D' requirement.

Python

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

pattern = "IIIDIDDD"
print(smallest_number_from_pattern(pattern))

Java

import java.util.Stack;

public class SmallestNumberFromPattern {
    public static String smallestNumber(String pattern) {
        StringBuilder result = new StringBuilder();
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i <= pattern.length(); i++) {
            stack.push(i + 1);
            if (i == pattern.length() || pattern.charAt(i) == 'I') {
                while (!stack.isEmpty()) {
                    result.append(stack.pop());
                }
            }
        }
        return result.toString();
    }

    public static void main(String[] args) {
        String pattern = "IIIDIDDD";
        System.out.println(smallestNumber(pattern));
    }
}

C++

#include <iostream>
#include <stack>
#include <string>

std::string smallestNumber(std::string pattern) {
    std::stack<int> stk;
    std::string result;

    for (int i = 0; i <= pattern.size(); i++) {
        stk.push(i + 1);
        if (i == pattern.size() || pattern[i] == 'I') {
            while (!stk.empty()) {
                result += std::to_string(stk.top());
                stk.pop();
            }
        }
    }
    return result;
}

int main() {
    std::string pattern = "IIIDIDDD";
    std::cout << smallestNumber(pattern) << std::endl;
    return 0;
}

JavaScript

function smallestNumber(pattern) {
    let result = "", stack = [];

    for (let i = 0; i <= pattern.length; i++) {
        stack.push(i + 1);

        if (i === pattern.length || pattern[i] === 'I') {
            while (stack.length > 0) {
                result += stack.pop();
            }
        }
    }
    return result;
}

let pattern = "IIIDIDDD";
console.log(smallestNumber(pattern));

#include <stdio.h>
#include <string.h>

void smallestNumber(const char* pattern, char* result) {
    int stack[10], top = -1, i;

    for (i = 0; i <= strlen(pattern); i++) {
        stack[++top] = i + 1;
        if (i == strlen(pattern) || pattern[i] == 'I') {
            while (top != -1) {
                sprintf(result + strlen(result), "%d", stack[top--]);
            }
        }
    }
}

int main() {
    char pattern[] = "IIIDIDDD";
    char result[20] = "";
    smallestNumber(pattern, result);
    printf("%s\n", result);
    return 0;
}

using System;
using System.Collections.Generic;
using System.Text;

class SmallestNumberFromPattern {
    public static string SmallestNumber(string pattern) {
        var result = new StringBuilder();
        var stack = new Stack<int>();

        for (int i = 0; i <= pattern.Length; i++) {
            stack.Push(i + 1);
            if (i == pattern.Length || pattern[i] == 'I') {
                while (stack.Count > 0) {
                    result.Append(stack.Pop());
                }
            }
        }
        return result.ToString();
    }

    static void Main(string[] args) {
        string pattern = "IIIDIDDD";
        Console.WriteLine(SmallestNumber(pattern));
    }
}

This Python code initiates a result string res and a stack. It iterates over the pattern plus one additional iteration. In each iteration, the next available number is pushed to the stack. When an 'I' or the end of the pattern is reached, the stack is popped to res to fulfill 'D' sequences by reversing the additions.

Complexity

Time Complexity: O(n) - where n is the length of the pattern because each element is pushed and popped once.
Space Complexity: O(n) - due to stack storage as needed during computation.

Try this approach in the editor

Approach 2: Construct from Left to Right

In this approach, we use two pointers and direct calculation of segments using 'D' marks to populate numbers into the result. We fill numbers in reverse order whenever a 'D' is encountered.

Python

def smallest_number_from_pattern(pattern):
    res, n = [], len(pattern)
    for i, ch in enumerate(pattern + 'I', 1):
        res.append(i)
        if ch == 'I':
            res[-(i - len(res) + 1):] = reversed(res[-(i - len(res) + 1):])
    return ''.join(map(str, res))

pattern = "IIIDIDDD"
print(smallest_number_from_pattern(pattern))

Java

public class SmallestNumberFromPattern {
    public static String smallestNumber(String pattern) {
        StringBuilder res = new StringBuilder();
        int n = pattern.length();
        for (int i = 0, j = 1; i <= n; i++, j++) {
            res.append(j);
            if (i == n || pattern.charAt(i) == 'I') {
                reverse(res, j - 1);
            }
        }
        return res.toString();
    }
    private static void reverse(StringBuilder sb, int last) {
        int start = sb.length() - 1;
        while (start < last) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(last));
            sb.setCharAt(last, temp);
            start++;
            last--;
        }
    }
    public static void main(String[] args) {
        String pattern = "IIIDIDDD";
        System.out.println(smallestNumber(pattern));
    }
}

C++

#include <iostream>
#include <string>

std::string smallestNumber(std::string pattern) {
    std::string res;
    int n = pattern.size();
    for (int i = 0, j = 1; i <= n; ++i, ++j) {
        res += std::to_string(j);
        if (i == n || pattern[i] == 'I') {
            std::reverse(res.end() - (j - (int)res.size()), res.end());
        }
    }
    return res;
}

int main() {
    std::string pattern = "IIIDIDDD";
    std::cout << smallestNumber(pattern) << std::endl;
    return 0;
}

JavaScript

function smallestNumber(pattern) {
    let result = "";
    for (let i = 0, j = 1; i <= pattern.length; i++, j++) {
        result += j;
        if (i === pattern.length || pattern[i] === 'I') {
            result = result.slice(0, j - result.length) + [...result.slice(j - result.length)].reverse().join('');
        }
    }
    return result;
}

let pattern = "IIIDIDDD";
console.log(smallestNumber(pattern));

#include <stdio.h>
#include <string.h>

void reverse(char* start, char* end) {
    while (start < end) {
        char temp = *start;
        *start++ = *end;
        *end-- = temp;
    }
}

void smallestNumber(const char* pattern, char* result) {
    int n = strlen(pattern), j = 1;
    for (int i = 0; i <= n; i++, j++) {
        sprintf(result + strlen(result), "%d", j);
        if (i == n || pattern[i] == 'I') {
            reverse(result + strlen(result) - j + (int)strlen(result), result + strlen(result) - 1);
        }
    }
}

int main() {
    char pattern[] = "IIIDIDDD";
    char result[20] = "";
    smallestNumber(pattern, result);
    printf("%s\n", result);
    return 0;
}

using System;
using System.Text;

class SmallestNumberFromPattern {
    public static string SmallestNumber(string pattern) {
        var res = new StringBuilder();
        int n = pattern.Length;
        for (int i = 0, j = 1; i <= n; i++, j++) {
            res.Append(j);
            if (i == n || pattern[i] == 'I') {
                Reverse(res, res.Length - j, res.Length - 1);
            }
        }
        return res.ToString();
    }
    private static void Reverse(StringBuilder sb, int start, int end) {
        while (start < end) {
            char temp = sb[start];
            sb[start] = sb[end];
            sb[end] = temp;
            start++;
            end--;
        }
    }
    static void Main(string[] args) {
        string pattern = "IIIDIDDD";
        Console.WriteLine(SmallestNumber(pattern));
    }
}

This solution adds numbers sequentially and reverses segments during 'I'. At each occurrence of 'I', it reverses the segment from the last 'I' or the start, ensuring minimal lexicographical order through efficient list slicing and reversing.

Complexity

Time Complexity: O(n)
Space Complexity: O(n) - storing numbers progressively.

Try this approach in the editor

Approach 3: Default Approach

TypeScript

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('');
}

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
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach with Stack	Time Complexity: O(n) - where n is the length of the pattern because each element is pushed and popped once. Space Complexity: O(n) - due to stack storage as needed during computation.
Construct from Left to Right	Time Complexity: O(n) Space Complexity: O(n) - storing numbers progressively.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Backtracking (Permutation Search)	O(9!)	O(n)	Understanding the constraint structure or building intuition before optimization
Greedy with Stack	O(n)	O(n)	Interview-friendly approach; handles long decreasing sequences cleanly
Construct from Left to Right (Segment Reversal)	O(n)	O(1)	When minimizing auxiliary structures and working directly on the result array

Frequently asked questions

Is Construct Smallest Number From DI String easy or hard?

Construct Smallest Number From DI String is typically classified as a medium-level problem. The logic becomes straightforward once you recognize that consecutive 'D' segments must be reversed. Identifying the greedy stack strategy is the main challenge.

Construct Smallest Number From DI String Python/Java solution

Most implementations follow the greedy stack pattern: iterate through the pattern, push the next digit, and pop the stack when encountering 'I'. This logic is easy to implement in Python, Java, C++, C, C#, or JavaScript because it only requires basic stack operations and string construction.

How to solve Construct Smallest Number From DI String in O(n)?

Scan the pattern from left to right while assigning digits in increasing order. Use a stack to delay output for 'D' sequences, then pop when an 'I' appears to produce a decreasing segment. Because each digit is processed once, the total complexity stays linear at O(n).

What is the best approach for Construct Smallest Number From DI String?

The greedy stack approach is the most widely used solution. Iterate through the DI pattern, push sequential digits onto a stack, and flush the stack whenever an 'I' appears or the pattern ends. This automatically reverses decreasing segments and produces the smallest valid number. The algorithm runs in O(n) time and O(n) space.

Is Construct Smallest Number From DI String asked at Google/Amazon/Meta?

Greedy pattern construction problems like this frequently appear in interviews at large tech companies. Variants of DI pattern or stack-based sequence construction have been reported in interviews at companies such as Amazon and Google because they test greedy reasoning and stack usage.

What data structure is used in Construct Smallest Number From DI String?

A stack is the primary data structure in the optimal solution. The stack temporarily stores digits until the algorithm determines where a decreasing segment ends, then pops elements to produce the correct order.

What is the time complexity of Construct Smallest Number From DI String?

The optimal greedy solutions run in O(n) time, where n is the length of the DI string. Each digit is pushed and popped at most once when using the stack approach. Space complexity is O(n) for the stack or O(1) for the segment-reversal variant.

Construct Smallest Number From DI String solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach with Stack

Approach 2: Construct from Left to Right

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Construct Smallest Number From DI String solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach with Stack

Approach 2: Construct from Left to Right

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems