Find permutation

Array String Stack Greedy

66.9% acceptance

Mar 31, 2026

728

151

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

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn find_permutation(s: String) -> Vec<i32> {
    let n = s.len() + 1;
    let mut result: Vec<i32> = (1..=n as i32).collect();
    let bytes = s.as_bytes();
    let mut i = 0;
    while i < bytes.len() {
      if bytes[i] == b'D' {
        let start = i;
        while i < bytes.len() && bytes[i] == b'D' {
          i += 1;
        }
        result[start..=i].reverse();
      } else {
        i += 1;
      }
    }
    result
  }
}