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
- Push increasing numbers onto a stack, flushing whenever an
'I'is seen or the pattern ends. - A run of
'D's accumulates on the stack and is flushed in reverse, producing a decreasing sequence. - This is the same construction as Find Permutation (484) and yields the lexicographically smallest result.
- 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 == nflush: 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.