Construct Smallest Number From DI String

Problem Description

Ah, the classic “Construct Smallest Number From DI String” problem! It’s like trying to arrange your sock drawer but with a twist. You have a string of characters, ‘D’ for “decrease” and ‘I’ for “increase,” and your mission, should you choose to accept it, is to create the smallest possible number that fits this pattern.

Imagine you’re at a party, and everyone is trying to line up for the buffet. The ‘I’s are the eager beavers who want to be at the front of the line, while the ‘D’s are the ones who are just a tad too cool to be first. Your job is to make sure everyone gets in line according to their preferences while keeping the smallest number possible at the front.

So, if you have a pattern like “IIDI”, you need to construct the smallest number that fits this pattern. Spoiler alert: it’s not as easy as it sounds!

Solution

Copy Code

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        ans = []
        stack = ['1']

        for c in pattern:
            maxSorFar = stack[-1]
            if c == 'I':
                while stack:
                    maxSorFar = max(maxSorFar, stack[-1])
                    ans.append(stack.pop())
            stack.append(chr(ord(maxSorFar) + 1))

        while stack:
            ans.append(stack.pop())

        return ''.join(ans)

Approach Explanation

The approach here is as clever as a cat in a room full of laser pointers. We use a stack to keep track of the numbers we’re constructing. As we iterate through the pattern, we check if we need to increase or decrease. When we hit an ‘I’, we pop from the stack until it’s empty, ensuring we’re adding the smallest possible numbers to our answer. If we encounter a ‘D’, we simply push the next number onto the stack.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the length of the pattern.
Space Complexity	O(n) as well, since we store the numbers in a stack and the answer list.

Real-World Example

Let’s say you’re organizing a game of musical chairs. The players (numbers) need to sit down according to the music (the pattern). When the music plays (an ‘I’), everyone rushes to sit down in the smallest available chair (the smallest number). When the music stops (a ‘D’), they have to wait and see who gets to sit down next. The goal is to make sure the smallest chair is always occupied first!

Similar Problems

If you enjoyed this problem, you might want to check out these similar challenges:

• 3-Sum Solution in Python
• 4-Sum Solution in Python
• Two Sum Solution in Python
• Three Sum Closest Solution in Python
• Subarray Sum Equals K Solution in Python

Language Links

If you want to see solutions in other languages, check them out below:

C++
Java