484

484. Find Permutation (Medium)

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'.

Companies: Google

Related Topics:
Array, String, Stack, Greedy

Similar Questions:

• Using a Robot to Print the Lexicographically Smallest String (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/find-permutation
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    vector<int> findPermutation(string s) {
        vector<int> ans{1};
        for (char c : s) {
            if (c == 'D') {
                ans.push_back(ans.back());
                for (int i = ans.size() - 2; i >= 0 && ans[i] == ans[i + 1]; --i) ans[i]++;
            } else {
                ans.push_back(ans.size() + 1);
            }
        }
        return ans;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/find-permutation
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    vector<int> findPermutation(string s) {
        int N = s.size(), mx = 0, d = s[0] == 'D';
        vector<int> cnt;
        for (int i = 0; i < N;) {
            int start = i++;
            while (i < N && s[i] == s[i - 1]) ++i;
            cnt.push_back(i - start);
        }
        vector<int> ans;
        for (int i = 0; i < cnt.size(); ++i) {
            int c = cnt[i];
            if (ans.empty()) ++c;
            if (d) {
                int n = ans.empty() ? c : mx - 1;
                mx = max(n, mx);
                for (int j = 0; j < c; ++j) ans.push_back(n--);
            } else {
                int n = mx + 1;
                for (int j = 0; j < c; ++j) ans.push_back(n++);
                if (i < cnt.size() - 1) ans.back() += cnt[i + 1];
                mx = ans.back();
            }
            d = 1 - d;
        }
        return ans;
    }
};