problemmediumalgorithmsleetcode-484leetcode 484leetcode484

Find Permutation

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

A permutation perm of n integers of all the integers in the range [1, n] can be represented as a string s of length n - 1 where:

  • s[i] == 'I' if perm[i] < perm[i + 1], and
  • s[i] == 'D' if perm[i] > perm[i + 1].

Given a string s, reconstruct the lexicographically smallest permutation perm and return it.

Examples

Example 1:

Input: s = "I"
Output: [1,2]
Explanation: [1,2] is the only legal permutation that can represented by s, where the number 1 and 2 construct an increasing relationship.

Example 2:

Input: s = "DI"
Output: [2,1,3]
Explanation: Both [2,1,3] and [3,1,2] can be represented as "DI", but since we want to find the smallest lexicographical permutation, you should return [2,1,3]

Constraints:

  • 1 <= s.length <= 10^5
  • s[i] is either 'I' or 'D'.

Solution

Method 1 – Stack-based Greedy Construction

Intuition

To get the lexicographically smallest permutation, we process the string from left to right, pushing numbers onto a stack. When we see an 'I' or reach the end, we pop all elements from the stack to the answer. This reverses the order for 'D' runs, ensuring the smallest permutation.

Approach

  1. Initialize an empty stack and an empty answer list.
  2. For each position i from 0 to n-1 (where n = len(s)+1):
    • Push i+1 onto the stack.
    • If at the end or s[i] == 'I', pop all elements from the stack and append to the answer.
  3. Return the answer list.

Code

C++
class Solution {
public:
    vector<int> findPermutation(string s) {
        vector<int> ans, stk;
        int n = s.size();
        for (int i = 0; i <= n; ++i) {
            stk.push_back(i+1);
            if (i == n || s[i] == 'I') {
                while (!stk.empty()) {
                    ans.push_back(stk.back());
                    stk.pop_back();
                }
            }
        }
        return ans;
    }
};
Go
func findPermutation(s string) []int {
    n := len(s)
    ans := []int{}
    stk := []int{}
    for i := 0; i <= n; i++ {
        stk = append(stk, i+1)
        if i == n || s[i] == 'I' {
            for len(stk) > 0 {
                ans = append(ans, stk[len(stk)-1])
                stk = stk[:len(stk)-1]
            }
        }
    }
    return ans
}
Java
class Solution {
    public int[] findPermutation(String s) {
        int n = s.length();
        int[] ans = new int[n+1];
        Deque<Integer> stk = new ArrayDeque<>();
        int idx = 0;
        for (int i = 0; i <= n; i++) {
            stk.push(i+1);
            if (i == n || s.charAt(i) == 'I') {
                while (!stk.isEmpty()) ans[idx++] = stk.pop();
            }
        }
        return ans;
    }
}
Kotlin
class Solution {
    fun findPermutation(s: String): IntArray {
        val n = s.length
        val ans = mutableListOf<Int>()
        val stk = ArrayDeque<Int>()
        for (i in 0..n) {
            stk.addLast(i+1)
            if (i == n || s[i] == 'I') {
                while (stk.isNotEmpty()) ans.add(stk.removeLast())
            }
        }
        return ans.toIntArray()
    }
}
Python
class Solution:
    def findPermutation(self, s: str) -> list[int]:
        ans, stk = [], []
        n = len(s)
        for i in range(n+1):
            stk.append(i+1)
            if i == n or s[i] == 'I':
                while stk:
                    ans.append(stk.pop())
        return ans
Rust
impl Solution {
    pub fn find_permutation(s: String) -> Vec<i32> {
        let n = s.len();
        let mut ans = Vec::new();
        let mut stk = Vec::new();
        for i in 0..=n {
            stk.push((i+1) as i32);
            if i == n || s.as_bytes()[i] == b'I' {
                while let Some(x) = stk.pop() {
                    ans.push(x);
                }
            }
        }
        ans
    }
}
TypeScript
class Solution {
    findPermutation(s: string): number[] {
        const n = s.length;
        const ans: number[] = [];
        const stk: number[] = [];
        for (let i = 0; i <= n; i++) {
            stk.push(i+1);
            if (i === n || s[i] === 'I') {
                while (stk.length) ans.push(stk.pop()!);
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s, since each number is pushed and popped once.
  • 🧺 Space complexity: O(n), for the stack and answer array.

Comments