Find Permutation

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:

1
2
3


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:

1
2
3


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

Initialize an empty stack and an empty answer list.
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.
Return the answer list.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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.

Problem#

Examples#

Solution#

Method 1 – Stack-based Greedy Construction#

Intuition#

Approach#

Code#

Complexity#