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]
Note:
1 <= S.length <= 10000
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 --;
}
}
}