Construct Smallest Number From DI String

Medium
1235.

Construct Smallest Number From DI String

Construct Smallest Number From DI String is a medium coding problem on strings, greedy and stack, asked in Amazon, Google and Goldman Sachs interviews.

You are given a string pattern of length n made of the letters 'I' (increasing) and 'D' (decreasing).

Build a string num of length n + 1 such that:

  • num uses only the digits '1' to '9', each digit 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 such string.

Example 1

Input
pattern = "DDI"
Output
3214
Explanation
The first three digits must fall, then rise; `3214` is the smallest way to do that.

Example 2

Input
pattern = "IDID"
Output
13254

Example 3

Input
pattern = "D"
Output
21

Constraints

  • 1 <= pattern.length <= 8
  • pattern consists of only the letters 'I' and 'D'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} pattern
 * @return {string}
 */
var smallestNumber = function(pattern) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Construct Smallest Number From DI String — Solution

Construct Smallest Number From DI String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Construct Smallest Number From DI String is a medium coding problem on strings, greedy and stack, asked in Amazon, Google and Goldman Sachs interviews.

Problem statement

You are given a string pattern of length n made of the letters 'I' (increasing) and 'D' (decreasing).

Build a string num of length n + 1 such that:

  • num uses only the digits '1' to '9', each digit 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 such string.

Example 1

Input: pattern = "DDI"
Output: 3214
Explanation: The first three digits must fall, then rise; `3214` is the smallest way to do that.

Example 2

Input: pattern = "IDID"
Output: 13254

Example 3

Input: pattern = "D"
Output: 21

Constraints

  • 1 <= pattern.length <= 8
  • pattern consists of only the letters 'I' and 'D'

Hints for Construct Smallest Number From DI String

  1. Hint 1

    If the pattern were all Is, the answer would be 1 2 3 …. What does a run of Ds do to that?

  2. Hint 2

    A run of k Ds needs k + 1 falling digits. Use the smallest unused digits for them, written in reverse.

  3. Hint 3

    Push i + 1 onto a stack for each position; whenever the pattern says I (or the string ends), pop the whole stack into the answer.

How to solve Construct Smallest Number From DI String

Start from the ascending sequence 1, 2, …, n + 1 and reverse each block that a run of Ds covers. A stack does those reversals on the fly.

Approach

  1. For i from 0 to n, push the digit i + 1 onto a stack.
  2. If i == n or pattern[i] == 'I', pop every digit off the stack and append it to the answer.
  3. Return the answer.

Why it works

Each maximal group of positions joined by Ds must be strictly decreasing, and consecutive groups are joined by an I. Using the digits in increasing order, each group receives the smallest digits still unused, placed in decreasing order — any smaller digit at the front of a group would have to be followed by an even smaller one that is already taken. The stack pushes the group's digits in increasing order and pops them in reverse exactly when the group ends at an I or at the end of the string. Digits 1 to n + 1 <= 9 always suffice.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Remember to flush the stack after the last position as well.
  • A purely greedy "smallest unused digit" choice fails on D: the first digit must leave room for the whole falling run.
  • The answer always uses exactly the digits 1..n+1.

Reference solution

Python

def smallestNumber(pattern: str) -> str:
    out = []
    stack = []
    for i in range(len(pattern) + 1):
        stack.append(str(i + 1))
        if i == len(pattern) or pattern[i] == "I":
            while stack:
                out.append(stack.pop())
    return "".join(out)

Java

public static String smallestNumber(String pattern) {
    StringBuilder sb = new StringBuilder();
    Deque<Integer> stack = new ArrayDeque<>();
    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()) sb.append(stack.pop());
        }
    }
    return sb.toString();
}

C++

string smallestNumber(string pattern) {
    string out;
    vector<char> st;
    int n = pattern.size();
    for (int i = 0; i <= n; i++) {
        st.push_back((char)('1' + i));
        if (i == n || pattern[i] == 'I') {
            while (!st.empty()) { out += st.back(); st.pop_back(); }
        }
    }
    return out;
}

JavaScript

var smallestNumber = function(pattern) {
    var out = "", stack = [];
    for (var i = 0; i <= pattern.length; i++) {
        stack.push(String(i + 1));
        if (i === pattern.length || pattern[i] === "I") {
            while (stack.length) out += stack.pop();
        }
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms