Prerequisites
Before attempting this problem, you should be comfortable with:
- Stacks - Understanding LIFO behavior to reverse sequences of elements
- Greedy Algorithms - Making locally optimal choices to achieve the lexicographically smallest result
- Array Manipulation - In-place reversal of subarrays and two-pointer techniques
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
- Initialize an empty result array and a stack.
- Iterate through positions
1ton:- If the character at position
i-1is 'I', pushionto the stack, then pop all elements from the stack into the result. - If the character is 'D', just push
ionto the stack.
- If the character at position
- After the loop, push
n+1onto the stack and pop all remaining elements into the result. - 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 resTime & Space Complexity
- Time complexity:
- Space complexity:
Where 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
- Initialize the result array as
[1, 2, 3, ..., n+1]. - 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.
- 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] = tempTime & Space Complexity
- Time complexity:
- Space complexity:
Where 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
- Initialize
result[0] = 1and iterate through the string. - 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.
- 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 resTime & Space Complexity
- Time complexity:
- Space complexity:
Where 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.