Katkat
Back

Construct smallest number from I/D pattern

AirbnbSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests greedy algorithm design and stack-based data structure manipulation to satisfy relative ordering constraints within a sequence of digits.

Problem Statement

You are given a pattern string S consisting only of characters 'I' (increasing) and 'D' (decreasing). Your goal is to construct the smallest possible positive integer (as a string) that satisfies the following conditions:

  1. The resulting number must have exactly len(S) + 1 digits.
  2. Each digit must be unique (using digits 1 through 9, and at most one 0 if necessary, though typical constraints use 1-9).
  3. For each character S[i]:
    • If S[i] == 'I', the digit at index i must be less than the digit at index i + 1.
    • If S[i] == 'D', the digit at index i must be greater than the digit at index i + 1.

Note: Since you want the smallest number, you should use digits from 1 to len(S) + 1 exactly once.

Function Signature

def construct_smallest_number(pattern: str) -> str:

Examples

Example 1: Input: pattern = "II" Output: "123" Explanation: 1 1 and 1 < 3. This satisfies the 'D' and 'I' sequence.

Constraints

  • 1 <= len(pattern) <= 8
  • The pattern contains only 'I' or 'D'.

Edge Cases

  • Single character patterns ("I" or "D").
  • Sequences with all 'I's or all 'D's.

Hints

Hint 1

Consider that since you want the smallest number, you should try to place the smallest available digits as early as possible.

Hint 2

When you encounter a sequence of 'D's, the numbers must be placed in decreasing order, effectively reversing a segment of the sequence.

Hint 3

A stack can be used to store indices; push numbers (1, 2, 3...) onto the stack and pop them when you encounter an 'I' or reach the end of the string.

Follow-up questions

  • How would your approach change if the pattern length was allowed to be up to 100, requiring digits 1-9 to be reused (i.e., not necessarily unique)?
  • What is the time and space complexity of your solution, and can it be optimized further?
  • If the input string could contain a third character '?' representing either 'I' or 'D', how would you modify the algorithm to ensure the lexicographically smallest result?