Find Permutation

How it works

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.

Steps

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.

Complexity

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

Where n is the size of the resultant array

Things to watch for

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.

from typing import List

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

class Solution {
public:
    vector<int> findPermutation(string s) {
        int n = s.length();
        vector<int> res(n + 1);
        res[0] = 1;
        int i = 1;

        while (i <= n) {
            res[i] = i + 1;
            int j = i;

            if (s[i - 1] == 'D') {
                while (i <= n && s[i - 1] == 'D') {
                    i++;
                }

                for (int k = j - 1, c = i; k <= i - 1; k++, c--) {
                    res[k] = c;
                }
            } else {
                i++;
            }
        }

        return res;
    }
};