Skip to content

484. Find Permutation πŸ”’

Description

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.

 

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 <= 105
  • s[i] is either 'I' or 'D'.

Solutions

Solution 1

Thinking

Build the lexicographically smallest permutation of \(1..n+1\) matching an \(I/D\) string. Smallest order wants an increasing sequence except where a descent is required.

Start from \(1,2,\ldots,n+1\) and reverse each segment that a run of \(D\) covers. Positions with \(I\) keep their relative order.

Reversing a \(D\)-run makes that interval decreasing and does not enlarge an untouched prefix, so the permutation is the smallest one.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def findPermutation(self, s: str) -> List[int]:
        n = len(s)
        ans = list(range(1, n + 2))
        i = 0
        while i < n:
            j = i
            while j < n and s[j] == 'D':
                j += 1
            ans[i : j + 1] = ans[i : j + 1][::-1]
            i = max(i + 1, j)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int[] findPermutation(String s) {
        int n = s.length();
        int[] ans = new int[n + 1];
        for (int i = 0; i < n + 1; ++i) {
            ans[i] = i + 1;
        }
        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && s.charAt(j) == 'D') {
                ++j;
            }
            reverse(ans, i, j);
            i = Math.max(i + 1, j);
        }
        return ans;
    }

    private void reverse(int[] arr, int i, int j) {
        for (; i < j; ++i, --j) {
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> findPermutation(string s) {
        int n = s.size();
        vector<int> ans(n + 1);
        iota(ans.begin(), ans.end(), 1);
        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && s[j] == 'D') {
                ++j;
            }
            reverse(ans.begin() + i, ans.begin() + j + 1);
            i = max(i + 1, j);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func findPermutation(s string) []int {
    n := len(s)
    ans := make([]int, n+1)
    for i := range ans {
        ans[i] = i + 1
    }
    i := 0
    for i < n {
        j := i
        for ; j < n && s[j] == 'D'; j++ {
        }
        reverse(ans, i, j)
        i = max(i+1, j)
    }
    return ans
}

func reverse(arr []int, i, j int) {
    for ; i < j; i, j = i+1, j-1 {
        arr[i], arr[j] = arr[j], arr[i]
    }
}

Comments