⚡Flashcard Drill➔
NeetCode #504LC-2375MediumBacktracking
← Back to All Problems

#504 · #2375 · Construct Smallest Number From DI String(根据模式串构造最小数字)

📌 Problem Statement & Constraints

You are given a string pattern of 'I' (increase) and 'D' (decrease). Return the lexicographically smallest permutation of 1..n+1 that matches the pattern. Constraints: 1 <= pattern.length <= 8.

💡 Core Algorithmic Approaches

  1. Push increasing numbers onto a stack, flushing whenever an 'I' is seen or the pattern ends.
  2. A run of 'D's accumulates on the stack and is flushed in reverse, producing a decreasing sequence.
  3. This is the same construction as Find Permutation (484) and yields the lexicographically smallest result.
  4. The flush order is what makes the leading digits as small as possible.

💻 Benchmark Python3 Implementation

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        res = []
        st = []
        n = len(pattern)
        for i in range(n + 1):
            st.append(i + 1)               # next candidate number
            if i == n or pattern[i] == "I":   # flush the pending decreasing run
                while st:
                    res.append(str(st.pop()))
        return "".join(res)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each number is pushed and popped once.
💾 Space Complexity
O(n) for the stack and the result.

⚠️ Interview Pitfalls & Follow-ups

  • Flushing on 'D' instead of 'I': the decreasing runs would not be built.
  • Forgetting the i == n flush: the last run would never be emitted.
  • Returning integers instead of a string: the API returns a string.
  • Trying a greedy assignment without a stack: the lexicographic minimality requires the run-reversal construction.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems