DI String match

Question

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) {
  int[] A = new int[S.length() + 1];
  char[] sCharArray = S.toCharArray();
    int indexForI = 0;
  int indexForD = S.length();

  for (int i = 0; i < S.length(); i++) {
   if (sCharArray[i] == 'I') {
    A[i] = indexForI++;
   } else {
    A[i] = indexForD--;
   }
  }
  A[S.length()] = indexForD;
  return A;
 }
}

Test Cases

  1. Test for input string having combination of ‘I’ and ’D’ for eg. “IDDDIDID”.
  2. Test for input string having only ‘I’ for eg. “IIIIII”.
  3. Test for input string having only ’D’ for eg. “DDDDD”.
  4. Test for input string having alternating ‘I’ and ’D’ for eg. “IDIDIDI”.
  5. Test for a single character string for eg. ‘I’.
  6. Test for the maximum string length.i.e. 10,000.
  7. Test for an empty string.
  8. Test for null string.(Exception is not handled here).

See also