Construct Smallest Number From DI String - Practice Coding Problems

Construct Smallest Number From DI String - 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.

Input & Output

Example 1 — Basic Decreasing-Increasing

$ Input: pattern = "DI"

› Output: "213"

💡 Note: For pattern "DI", we need num[0] > num[1] (D) and num[1] < num[2] (I). Using digits [1,2,3], the arrangement "213" satisfies: 2 > 1 (D) and 1 < 3 (I).

Example 2 — All Increasing

$ Input: pattern = "III"

› Output: "1234"

💡 Note: Pattern "III" means all positions should be increasing. The lexicographically smallest arrangement is "1234": 1 < 2 < 3 < 4.

Example 3 — All Decreasing

$ Input: pattern = "DDI"

› Output: "3214"

💡 Note: Pattern "DDI" needs two decreasing positions followed by increasing. Starting with [1,2,3,4], reverse the D-segment [1,2,3] to get [3,2,1,4], giving "3214".

Constraints

1 ≤ pattern.length ≤ 8
pattern contains only characters 'I' and 'D'

Visualization

Tap to expand

Understanding the Visualization

Input

Pattern string with 'D' (decreasing) and 'I' (increasing) characters

Process

Use stack to handle D-sequences, pop on I or end

Output

Lexicographically smallest number string satisfying all constraints

Key Takeaway

🎯 Key Insight: Stack naturally handles decreasing sequences while maintaining lexicographic optimality

Asked in

G Google 25 a Amazon 18 M Microsoft 12 F Facebook 8

The key insight is to use a stack to handle decreasing sequences efficiently. When we encounter 'D', we accumulate digits in a stack, and when we see 'I' (or reach the end), we pop all digits to reverse the decreasing segment. Best approach is Stack Method with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Permutations	O((n+1)!)	O(n)	Generate all possible digit arrangements and find the smallest valid one
Greedy Approach	O(n)	O(n)	Build result greedily by choosing smallest available digit for each position
Stack Approach	O(n)	O(n)	Use a stack to handle decreasing sequences efficiently

Brute Force - Try All Permutations — Algorithm Steps

Generate all permutations of digits 1 to n+1
For each permutation, check if it satisfies the I/D pattern
Return the lexicographically smallest valid permutation

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Permutations

Create all possible arrangements of digits 1 to n+1

Check Pattern

For each permutation, verify it follows I/D rules

Return First Valid

Return the lexicographically smallest valid arrangement

Code -

solution.c — C

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

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int checkValid(int* nums, char* pattern, int n) {
    for (int i = 0; i < n; i++) {
        if (pattern[i] == 'I' && nums[i] >= nums[i + 1]) {
            return 0;
        }
        if (pattern[i] == 'D' && nums[i] <= nums[i + 1]) {
            return 0;
        }
    }
    return 1;
}

char* permute(int* nums, char* pattern, int start, int n, char* result) {
    if (start == n + 1) {
        if (checkValid(nums, pattern, n)) {
            for (int i = 0; i <= n; i++) {
                result[i] = '0' + nums[i];
            }
            result[n + 1] = '\0';
            return result;
        }
        return NULL;
    }
    
    for (int i = start; i <= n; i++) {
        swap(&nums[start], &nums[i]);
        char* res = permute(nums, pattern, start + 1, n, result);
        if (res != NULL) {
            return res;
        }
        swap(&nums[start], &nums[i]);
    }
    return NULL;
}

char* solution(char* pattern) {
    int n = strlen(pattern);
    int* nums = (int*)malloc((n + 1) * sizeof(int));
    char* result = (char*)malloc((n + 2) * sizeof(char));
    
    for (int i = 0; i <= n; i++) {
        nums[i] = i + 1;
    }
    
    char* res = permute(nums, pattern, 0, n, result);
    free(nums);
    
    return res ? res : "";
}

int main() {
    char pattern[10];
    fgets(pattern, sizeof(pattern), stdin);
    pattern[strcspn(pattern, "\n")] = 0;
    
    char* result = solution(pattern);
    printf("%s\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((n+1)!)

Generate (n+1)! permutations and check each one

✓ Linear Growth

Space Complexity

O(n)

Store current permutation and result string

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler