LeetCode 484 — Find permutation

In this article, I will introduce LeetCode #484, find permutation.

The question is given a string that contains the combination of ‘I’ and ‘D’. These two characters mean the following two conditions:

# s is input string, i is the index of character
# output is the final results
c = s[i]
If c == 'I':
    output[i] < output[i+1]
if c == 'D':
    output[i] > output[i+1]

You could think of like when the next command is ‘I’, the next number is increasing. When the next command is ‘D’, the next number is decreasing.

Since there could be multiple permutations that fit the first constraint, the second constraint is that the final output should be a minimal lexicographic permutation. It ensures that the final output is unique.

Solution: Stack

Because of the second constraint, we could think that we want to have the permutation close to the increasing order like [1, 2, 3, 4, 5] when the input is ‘IDDI’.

The idea is that we consider ‘I’ as the border to separate the decreasing regions and increasing regions. And we store the numbers we want to add in the stack. We can think about the stack when we see questions related to the reverse string.

We then put the number into the stack when we encounter ‘D’ because we need to reverse them. Once we encounter ‘I’, it means that the reverse ends, so we pop out all the numbers in the stack.

We start from 1 and put the current number into the stack. The first command is ‘I’. It means that we want to have a number larger than 1. So we pop 1 out of the stack and add it into the output list. Then add the current number 2 into the stack.

The second command is ‘D’, so we add 3 into the stack. Now the stack contains [2, 3].

The third command is also ‘D’, then we add 4 into the stack as well. Now the stack contains [2, 3, 4].

The fourth command is ‘I’. Now we can stop the reversing. So we pop out all the numbers in the stack and add them into output. After pop out all the numbers, the output is [1, 4, 3, 2]. After pop out all the numbers, we add 5 into the stack as well.

In the end, we just need to pop out all the numbers in the stack and add them to the output list. We finally get [1, 4, 3, 2, 5].

Sample Code

def findPermutation(self, s: str) -> List[int]:
    n = len(s) + 1
    stack = [1]
    cur = 1
    output = []
    for i in s:
        cur += 1
        if i == 'D':
            stack.append(cur)
        else:
            while stack:
                output.append(stack.pop())
            stack.append(cur)
    while stack:
        output.append(stack.pop())
return output