Problem

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.

Examples

Example 1

1
2

Input: s = "IDID"
Output: [0,4,1,3,2]

Example 2

1
2

Input: s = "III"
Output: [0,1,2,3]

Example 3

1
2

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

Constraints

  • 1 <= s.length <= 10^5
  • s[i] is either 'I' or 'D'.

Solution

Method 1 – Two Pointers (Greedy)

Intuition

We want to construct a permutation of [0, n] such that for each character in s:

  • If s[i] == ‘I’, then perm[i] < perm[i+1]
  • If s[i] == ‘D’, then perm[i] > perm[i+1]

The greedy way is to use two pointers: one starting at 0 (lo), one at n (hi). For each ‘I’, pick lo and increment; for each ‘D’, pick hi and decrement. This guarantees the required order.

Approach

  1. Initialize lo = 0 and hi = n (where n = len(s)).
  2. For each character in s:
    • If ‘I’, append lo to ans and increment lo.
    • If ‘D’, append hi to ans and decrement hi.
  3. After the loop, append the last remaining number (lo == hi).
  4. Return the constructed permutation.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    vector<int> diStringMatch(string s) {
        int n = s.size(), lo = 0, hi = n;
        vector<int> ans;
        for (char c : s) {
            if (c == 'I') ans.push_back(lo++);
            else ans.push_back(hi--);
        }
        ans.push_back(lo);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func diStringMatch(s string) []int {
    n := len(s)
    lo, hi := 0, n
    ans := make([]int, 0, n+1)
    for _, c := range s {
        if c == 'I' {
            ans = append(ans, lo)
            lo++
        } else {
            ans = append(ans, hi)
            hi--
        }
    }
    ans = append(ans, lo)
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int[] diStringMatch(String s) {
        int n = s.length(), lo = 0, hi = n;
        int[] ans = new int[n+1];
        for (int i = 0; i < n; ++i) {
            ans[i] = s.charAt(i) == 'I' ? lo++ : hi--;
        }
        ans[n] = lo;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun diStringMatch(s: String): IntArray {
        val n = s.length
        var lo = 0
        var hi = n
        val ans = IntArray(n+1)
        for (i in s.indices) {
            ans[i] = if (s[i] == 'I') lo++ else hi--
        }
        ans[n] = lo
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def diStringMatch(self, s: str) -> list[int]:
        n = len(s)
        lo, hi = 0, n
        ans = []
        for c in s:
            if c == 'I':
                ans.append(lo)
                lo += 1
            else:
                ans.append(hi)
                hi -= 1
        ans.append(lo)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn di_string_match(s: String) -> Vec<i32> {
        let n = s.len();
        let (mut lo, mut hi) = (0, n as i32);
        let mut ans = Vec::with_capacity(n+1);
        for c in s.chars() {
            if c == 'I' {
                ans.push(lo);
                lo += 1;
            } else {
                ans.push(hi);
                hi -= 1;
            }
        }
        ans.push(lo);
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    diStringMatch(s: string): number[] {
        const n = s.length;
        let lo = 0, hi = n;
        const ans: number[] = [];
        for (const c of s) {
            if (c === 'I') ans.push(lo++);
            else ans.push(hi--);
        }
        ans.push(lo);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s. We process each character once.
  • 🧺 Space complexity: O(n), for the output array.