Today’s problem

https://leetcode.com/problems/construct-smallest-number-from-di-string/

Intuition

This problem let us find a sequence of numbers under some constrains.

First we observe that the N, the length of the sequence, is very small. Thereofre, we can use a dfs to traverse all possible situations and get the result.

Another way to do that is using a stack. When the array is increasing, the smallest way to get a valid array is to traverse all the numbers, filling in the smallest number possible. When the array is decreasing, becuase we still want the smallest array, we need to put the smallest number available, which should be also larger to the next number. In this case, the smallest number we can put at current place is the position + the number of consequtive ‘D’s afterward. Therefore, we can use a stack to temporarily sotre the number we are traversing, and add it back to the current array when we meet a ‘I’ or reach to the end of the array.

Approach

For Solution 1, the dfs solution, all we need to do is to traverse all the solutions and get the first one that fullfills the requirement.

For Solution 2, the stack solution, when we meet ‘I’, we can put “idx + 1” to our current array, then fill all the elements in a stack into our current array in reverse order, then flush the stack. When we meet ‘D’, we can put “idx + 1” to our stack for our future use.

Trick

• DFS: Because we are required to find the smallest valid sequence, so the first sequence that is not None is our target. This means that we can return this answer as soon as we get a valid result.

• Stack: Here I intentionally add a “D” to the end of the sequence. Intuitively speaking, the last element is the largest element in the sequence, so to put it into our current sequence, it requires a “D” operation. In this case, if the original last character is ‘I’, then we can directlly put the largest number to the end of our original sequence, which is the same as a ‘D’ operation. This is because the ‘I’ operation will flush the stack, so there will only be one element in the stack, making it the same whether adding as a normal sequence or a inverted sequence. If the original last character is ‘D’, then the largest character should be at the position whether the consequtive sequence of ‘D’ starts. In this case, this means that there should be a ‘D’ operation to put this number into the right position. Though this trick makes the code more tidy and elegant, it sacrifices readability, which is not encouraged.

Complexity

• Time complexity for dfs solution: $O(N!)$, N is the length of the sequence.

• Time complexity for stack solution: $O(N)$, N is the length of the sequence.

• Space complexity for dfs solution: $O(N)$, N is the length of the sequence.

• Space complexity for stack solution: $O(N)$, N is the length of the sequence.

Code

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        arr = []
        n = len(pattern) + 2
        def dfs(arr):
            if len(arr) == n - 1:
                return arr
            now = len(arr) - 1
            res = None
            if pattern[now] == 'I':
                for i in range(arr[now] + 1, n):
                    if i not in arr:
                        res = dfs(arr + [i])
                        if res is not None:
                            return res
            else:
                for i in range(1, arr[now]):
                    if i not in arr:
                        res = dfs(arr + [i])
                        if res is not None:
                            return res
            
            return res


        for i in range(1, n):
            ans = dfs([i])
            if ans is not None:
                return ''.join(map(str, ans))
                # return ans
        
        return None

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        arr = []
        n = len(pattern) + 2
        def dfs(arr):
            if len(arr) == n - 1:
                return arr
            now = len(arr) - 1
            res = None
            if pattern[now] == 'I':
                for i in range(arr[now] + 1, n):
                    if i not in arr:
                        res = dfs(arr + [i])
                        if res is not None:
                            return res
            else:
                for i in range(1, arr[now]):
                    if i not in arr:
                        res = dfs(arr + [i])
                        if res is not None:
                            return res
            
            return res


        for i in range(1, n):
            ans = dfs([i])
            if ans is not None:
                return ''.join(map(str, ans))
                # return ans
        
        return None

For more solutions, please visit My blog.