#484 - Find Permutation

Medium • View on LeetCode • View on GitHub

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

Solution

/**
 * @param {string} s
 * @return {number[]}
 */
var findPermutation = function(s) {
  const n = s.length + 1;
  const result = new Array(n).fill(0).map((_, i) => i + 1);

  for (let i = 0; i < s.length; i++) {
    if (s[i] === 'D') {
      let start = i;
      while (i < s.length && s[i] === 'D') {
        i++;
      }
      let end = i;
      while (start < end) {
        [result[start], result[end]] = [result[end], result[start]];
        start++;
        end--;
      }
      i--;
    }
  }

  return result;
};