Find Permutation - Solution & Explanation

Problem Overview: You are given a string consisting of characters 'I' (increasing) and 'D' (decreasing). The goal is to construct the lexicographically smallest permutation of numbers 1..n that satisfies this pattern. If s[i] = 'I', then perm[i] < perm[i+1]; if 'D', then perm[i] > perm[i+1].

Approach 1: Brute Force Permutation Search (O(n! * n) time, O(n) space)

Generate all permutations of numbers 1..n and check which ones satisfy the pattern. For each permutation, iterate through the pattern and verify whether adjacent elements follow the required increasing or decreasing rule. The first valid permutation in lexicographical order is the answer. This approach works conceptually but becomes infeasible quickly because the number of permutations grows factorially.

Approach 2: Greedy with Segment Reversal (O(n) time, O(1) extra space)

Start by building a sequence [1,2,3,...,n]. Traverse the pattern and look for consecutive 'D' segments. Whenever a block of 'D' appears from index i to j, reverse the corresponding range in the permutation. Reversing transforms the increasing sequence into the required decreasing structure while keeping the permutation lexicographically minimal. This greedy idea works because the smallest numbers are placed as early as possible while only adjusting ranges that violate the pattern.

Approach 3: Stack-Based Greedy (O(n) time, O(n) space)

This is the most common interview solution. Iterate through indices from 1 to n and push each number onto a stack. Whenever you encounter an 'I' or reach the end of the pattern, pop all elements from the stack and append them to the result. The stack naturally reverses segments corresponding to 'D' runs, producing decreasing subsequences while preserving the smallest available numbers. The algorithm performs one pass through the pattern and uses stack push/pop operations, making it both simple and efficient.

The stack and reversal strategies rely on the same greedy insight: delay output while reading 'D', then release numbers in reverse order to enforce decreasing constraints. This pattern manipulation frequently appears in stack and greedy problems involving sequences.

Recommended for interviews: The stack-based greedy solution is what most interviewers expect. It runs in O(n) time with O(n) space and clearly demonstrates understanding of pattern processing. Mentioning the brute force approach shows baseline reasoning, but implementing the greedy stack solution proves you can optimize using insights about array ordering and pattern constraints.