# The DI (Decreasing/Increasing) String Match Algorithm

json-data

Your task is to return an array (that contains integer numbers from 0 to N, N is the length of a given string S that contains only I or D – denoting Increasing or Decreasing sequence) that satisfies for all i = 0 to i = N – 1.

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”.

The return array is size of N+1 (containing the numbers from 0 to N), if the first string character is I – then we can safely put 0 in the return permutation array – otherwise, we can safely put N at the beginning.

We define two number indicators at both end, moving towards each other, at the end, they will meet in the middle where low = high, and we just need to set this number to the last element in the return permutation. The Java implementation of such string match algorithm is:

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ``` ```class Solution {     public int[] diStringMatch(String S) {         int sz = S.length();         int lo = 0;         int hi = sz;         int[] r = new int[sz + 1];         for (int i = 0; i < sz; ++ i) {             if (S.charAt(i) == 'I') {                 r[i] = lo ++;             } else {                 r[i] = hi --;             }         }         r[sz] = lo;         return r;     } }```
```class Solution {
public int[] diStringMatch(String S) {
int sz = S.length();
int lo = 0;
int hi = sz;
int[] r = new int[sz + 1];
for (int i = 0; i < sz; ++ i) {
if (S.charAt(i) == 'I') {
r[i] = lo ++;
} else {
r[i] = hi --;
}
}
r[sz] = lo;
return r;
}
}```

O(N) runtime complexity as well as the space complexity – and the below C++ uses the STL::vector container – but the idea is the same.

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ``` ```class Solution { public:     vector diStringMatch(string S) {         vector r(S.size() + 1);         int lo = 0, hi = S.size();         for (int i = 0; i < S.size(); ++ i) {             if (S[i] == 'I') {                 r[i] = lo ++;             } else {                 r[i] = hi --;             }         }         r[S.size()] = hi;         return r;     } };```
```class Solution {
public:
vector diStringMatch(string S) {
vector r(S.size() + 1);
int lo = 0, hi = S.size();
for (int i = 0; i < S.size(); ++ i) {
if (S[i] == 'I') {
r[i] = lo ++;
} else {
r[i] = hi --;
}
}
r[S.size()] = hi;
return r;
}
};```

GD Star Rating