Leetcode problem 85 - DI String Match

A permutation perm of n + 1 integers of all the integers in the range [0, n] can be represented as a string s of length n 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 permutation perm and return it. If there are multiple valid permutations perm, return any of them.

Example 1:

Input: s = “IDID” Output: [0,4,1,3,2] Example 2:

Input: s = “III” Output: [0,1,2,3] Example 3:

Input: s = “DDI” Output: [3,2,0,1]

/**
 * @param {string} s
 * @return {number[]}
 */
var diStringMatch = function (s) {
  let max = s.length + 1; // Initialize max value to the length of the input string plus 1
  let min = -1; // Initialize min value to -1
  let result = []; // Initialize an empty array to store the result

  // Iterate over each character of the input string and determine the values based on "I" and "D"
  for (let i = 0; i <= s.length; i++) {
    // If the current character is "I", increment min and push it to the result array
    if (s[i] == "I") {
      min++;
      result.push(min);
    } else {
      // If the current character is "D", decrement max and push it to the result array
      max--;
      result.push(max);
    }
  }

  // Return the final result array
  return result;
};

The time complexity of the loop is O(n), where n is the length of the input string s. The loop iterates over each character of the string.

The loop iterates through each character of the input string, resulting in a space complexity of O(n), where n is the length of s.