Di string match

Array Two Pointers String Greedy

80.9% acceptance

Feb 25, 2026

2603

1080

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn di_string_match(s: String) -> Vec<i32> {
    let n = s.len();
    let mut lo = 0i32;
    let mut hi = n as i32;
    let mut res = Vec::with_capacity(n + 1);
    for c in s.chars() {
      if c == 'I' {
        res.push(lo);
        lo += 1;
      } else {
        res.push(hi);
        hi -= 1;
      }
    }
    res.push(lo);
    res
  }
}