1. Using Stack

Intuition

To produce the lexicographically smallest permutation, we want to place smaller numbers as early as possible. The string tells us the relationship between consecutive elements: 'I' means increasing, 'D' means decreasing. When we encounter a sequence of 'D's, we need to reverse the order of those numbers. A stack naturally handles this: push numbers onto the stack during 'D' sequences, then pop them all when we hit an 'I' (or the end), which reverses their order.

Algorithm

1. Initialize an empty result array and a stack.
2. Iterate through positions 1 to n:
   • If the character at position i-1 is 'I', push i onto the stack, then pop all elements from the stack into the result.
   • If the character is 'D', just push i onto the stack.
3. After the loop, push n+1 onto the stack and pop all remaining elements into the result.
4. Return the result array.

class Solution:
    def findPermutation(self, s: str) -> List[int]:
        res = [0] * (len(s) + 1)
        stack = []
        j = 0

        for i in range(1, len(s) + 1):
            if s[i - 1] == 'I':
                stack.append(i)
                while stack:
                    res[j] = stack.pop()
                    j += 1
            else:
                stack.append(i)

        stack.append(len(s) + 1)
        while stack:
            res[j] = stack.pop()
            j += 1

        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

Where $n$ is the number of elements in the resultant arrangement

---

2. Reversing the Subarray

Intuition

Start with the identity permutation [1, 2, ..., n+1], which is already the smallest possible arrangement. Whenever we see a sequence of consecutive 'D's, we need those corresponding elements to be in decreasing order. We can achieve this by reversing the subarray that spans those 'D's. This maintains the smallest possible values in earlier positions while satisfying the decrease constraints.

Algorithm

1. Initialize the result array as [1, 2, 3, ..., n+1].
2. Iterate through the string:
   • When a 'D' is encountered, find the end of the consecutive 'D' sequence.
   • Reverse the subarray from the position before the first 'D' to the position after the last 'D'.
   • Continue from after the reversed segment.
3. Return the modified result array.

class Solution:
    def findPermutation(self, s: str) -> List[int]:
        n = len(s)
        res = [i + 1 for i in range(n + 1)]

        i = 1

        while i <= n:
            j = i

            while i <= n and s[i - 1] == 'D':
                i += 1

            self.reverse(res, j - 1, i)
            i += 1

        return res

    def reverse(self, a: List[int], start: int, end: int) -> None:
        for i in range((end - start) // 2):
            temp = a[i + start]
            a[i + start] = a[end - i - 1]
            a[end - i - 1] = temp

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$

Where $n$ is the size of the resultant array

---

3. Two Pointers

Intuition

We can build the result directly without explicitly reversing subarrays. For 'I' characters, we simply place the next available number. For 'D' sequences, we need to place a decreasing run of numbers. When we find a sequence of k consecutive 'D's, we fill those k+1 positions with decreasing values starting from the highest value in that range. This is done by identifying the 'D' segment boundaries and filling values in reverse order.

Algorithm

1. Initialize result[0] = 1 and iterate through the string.
2. For each position:
   • If the character is 'I', set the default value for the current position.
   • If the character is 'D', find the entire consecutive 'D' sequence.
   • Fill the positions covered by this 'D' sequence with decreasing values.
3. Return the result array.

class Solution:
    def findPermutation(self, s: str) -> List[int]:
        n = len(s)
        res = [0] * (n + 1)
        res[0] = 1
        i = 1

        while i <= n:
            res[i] = i + 1
            j = i

            if s[i - 1] == 'D':
                while i <= n and s[i - 1] == 'D':
                    i += 1

                k, c = j - 1, i
                while k <= i - 1:
                    res[k] = c
                    k += 1
                    c -= 1
            else:
                i += 1

        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$

Where $n$ is the size of the resultant array

Common Pitfalls

Forgetting to Handle the Final Element

The result array has n+1 elements for a string of length n. After processing all characters in the string, you must still handle the last number (n+1). Whether using a stack or reversing approach, forgetting to process this final element results in an incomplete permutation with missing or zero values.

Misunderstanding the Stack's Role

When using a stack approach, the stack reverses the order of consecutive numbers during 'D' sequences. A common mistake is popping immediately on every character instead of accumulating during 'D' runs and only popping when encountering 'I'. This leads to incorrect orderings that do not satisfy the decrease constraints.

Off-by-One Index Errors

The string uses 0-based indexing while the permutation uses values 1 to n+1. Converting between string indices and permutation values requires careful attention. For example, s[i-1] corresponds to the relationship between positions i and i+1 in the result. Confusing these mappings produces permutations that do not match the input pattern.