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:

 

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]
 

Note:

  1. 1 <= S.length <= 10000
  2. S only contains characters "I" or "D".

Solution:

class Solution {
    public int[] diStringMatch(String S) {
        //   I D I D
        // 0 2 1 4 3
        //   D D I
        // 2 1 0 3
        int[] res = new int[S.length() + 1];
        for (int i = 1; i < res.length; i ++) {
            res[i] = i;
        }
        int i = 0;
        for (int j = 0; j < S.length(); j ++) {
            if (S.charAt(j) == 'D') {
                // System.out.println(i + ", " + j);
                Arrays.sort(res, i, j + 2);
                swap(res, i, j + 1);
            } else {
                i = j + 1;
            }
        }
        return res;
    }
    
    private void swap(int[] arr, int left, int right) {
        while (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left ++;
            right --;
        }
    }
}