LeetCode 942: DI String Match

Explanation:

To solve this problem, we can start by observing that the permutation is always [0, 1, 2, ..., n] in ascending order. The given string s determines whether the next number in the permutation should be the current minimum or maximum available number.

We can iterate through the string s and maintain two pointers, one pointing to the minimum number available and the other pointing to the maximum number available. If we encounter an 'I', we pick the minimum number available, and if we encounter a 'D', we pick the maximum number available.

class Solution {
    public int[] diStringMatch(String s) {
        int n = s.length();
        int[] perm = new int[n + 1];
        int min = 0, max = n;
        
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'I') {
                perm[i] = min++;
            } else {
                perm[i] = max--;
            }
        }
        
        perm[n] = min; // or max, as they are equal at this point
        
        return perm;
    }
}