942. DI String Match

Given a string S that only contains "I" (increase) or "D" (decrease), let N = S.length.

Return any permutation A of [0, 1, ..., N] such that for all i = 0, ..., N-1:

If S[i] == "I", then A[i] < A[i+1]
If S[i] == "D", then A[i] > A[i+1]


Example 1:

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

Example 2:

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

Example 3:

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


Solution:

From the above examples, we can see if the first character is "I", we should choose the smallest number in the range, which is 0. And if the first character is "D", we need to choose the largest number in the range, which is N.

After each choice, we shrink the range.

From the second character, we apply the same logic.

Therefore, we can solve this problem in O(n) time.


Code:

class Solution {
    public int[] diStringMatch(String S) {
        int N = S.length();
        int increase = 0;
        int decrease = N;
        int[] res = new int[N + 1];
        for (int i = 0; i < N; i++) {
            char c = S.charAt(i);
            if (c == 'I') {
                res[i] = increase++;
            } else { // c == 'D'
                res[i] = decrease--;
            }
        }
        res[N] = increase;
        return res;
    }
}