Problem Description

The Find Permutation problem asks you to reconstruct a permutation of the first n positive integers (that is, the numbers from 1 to n, each used exactly once, in some order) given a string s consisting only of the characters 'D' (for "decrease") and 'I' (for "increase").

The string s has length n-1. For each character in s:

• If s[i] == 'I', then the i-th element of the permutation must be less than the i+1-th element.
• If s[i] == 'D', then the i-th element must be greater than the i+1-th element.

You must return any one valid permutation that satisfies all the constraints, and you must not reuse elements (each number from 1 to n can appear only once).

Thought Process

At first glance, you might think of generating all possible permutations of the numbers from 1 to n and checking which ones satisfy the 'D' and 'I' constraints. However, this brute-force approach is highly inefficient, as the number of permutations grows factorially with n.

To optimize, we should look for a way to construct the permutation directly, using the information in s as we build the answer. The key insight is that every 'D' requires a local decrease and every 'I' requires an increase, and we can use the smallest and largest available numbers to enforce these relationships as we go.

Instead of trying every possibility, we can build the sequence from left to right, always maintaining the required relationships by choosing the next available minimum or maximum number.

Solution Approach

We can solve this problem efficiently using a greedy approach. Here’s how:

• We maintain two pointers: low and high, initially set to 1 and n respectively.
• We iterate through the string s:
  • If s[i] == 'I', we append low to our result and increment low (because we want the next number to be higher).
  • If s[i] == 'D', we append high to our result and decrement high (because we want the next number to be lower).
• After processing all characters, one number remains (since the string is length n-1), so we append the last remaining number (which will be equal to low or high, since they are equal at this point).

This approach guarantees that each constraint is satisfied and every number from 1 to n is used exactly once.

Example Walkthrough

Let's walk through an example with s = "DID" (so n = 4).

1. Initialize low = 1, high = 4, result = [].
2. First character is 'D':
   • Append high = 4 to result: [4].
   • Decrement high to 3.
3. Second character is 'I':
   • Append low = 1: [4, 1].
   • Increment low to 2.
4. Third character is 'D':
   • Append high = 3: [4, 1, 3].
   • Decrement high to 2.
5. Append the last remaining number (low = 2): [4, 1, 3, 2].

This sequence satisfies all the 'D' and 'I' constraints.

Code Implementation

class Solution:
    def findPermutation(self, s: str) -> list[int]:
        n = len(s) + 1
        low, high = 1, n
        res = []
        for c in s:
            if c == 'I':
                res.append(low)
                low += 1
            else:  # 'D'
                res.append(high)
                high -= 1
        res.append(low)  # low == high here
        return res
      

class Solution {
public:
    vector<int> findPermutation(string s) {
        int n = s.length() + 1;
        int low = 1, high = n;
        vector<int> res;
        for (char c : s) {
            if (c == 'I') {
                res.push_back(low++);
            } else {
                res.push_back(high--);
            }
        }
        res.push_back(low); // low == high
        return res;
    }
};
      

class Solution {
    public int[] findPermutation(String s) {
        int n = s.length() + 1;
        int low = 1, high = n;
        int[] res = new int[n];
        int idx = 0;
        for (char c : s.toCharArray()) {
            if (c == 'I') {
                res[idx++] = low++;
            } else {
                res[idx++] = high--;
            }
        }
        res[idx] = low; // low == high
        return res;
    }
}
      

var findPermutation = function(s) {
    let n = s.length + 1;
    let low = 1, high = n;
    let res = [];
    for (let c of s) {
        if (c === 'I') {
            res.push(low++);
        } else {
            res.push(high--);
        }
    }
    res.push(low); // low === high
    return res;
};
      

Time and Space Complexity

• Brute-force approach:
  • Time: O(n!) (generating all permutations)
  • Space: O(n) (for a single permutation, but much more if storing all)
• Optimized greedy approach (above):
  • Time: O(n) — We process each character in s once.
  • Space: O(n) — We store the result permutation of length n.

The greedy method is exponentially faster and uses minimal extra space.

Summary

The Find Permutation problem can be solved efficiently by recognizing that each 'I' or 'D' in the string dictates a relationship between adjacent numbers in the permutation. By always choosing the current smallest or largest available number, we can construct a valid permutation in a single pass. This greedy approach is both simple and highly efficient, making it a great example of how understanding the constraints can lead to an elegant solution.