Problem Explanation

You are given a string consisting of only 'I' and 'D'. The string length is N. You need to return an array of length N+1 such that:

• When the ith character in S is 'I', the element at the ith index of the array is less than the element at the (i+1)th index of the array
• When the ith character in S is 'D', the element at the ith index of the array is greater than the element at the (i+1)th index of the array

Example

If the string S = "IDID", then a possible output could be the array: [0, 4, 1, 3, 2]. The conditions are satisfied because for i=0...N-1:

• If S[0] == I, then A[0] is less than A[1]
• If S[1] == D, then A[1] is greater than A[2]
• If S[2] == I, then A[2] is less than A[3]
• If S[3] == D, then A[3] is greater than A[4]

Approach/Solution

The solution uses a greedy algorithm with two pointers, min and max. We initialize min and max to be equal to the first and last indices of the possible output array, 0 and N respectively.

We then iterate through the input string S. If the character is 'I' we append min to the output array and increment min. If the character is 'D' we append max to the output array and decrement max.

At the end of the loop, we append min to the array. This is because min is now guaranteed to be within the remaining range of unused numbers, since we have been building the array by taking from either end.

Python Solution

1
2python
3class Solution:
4    def diStringMatch(self, S: str) -> List[int]:
5        min, max = 0, len(S)
6        ans = []
7        for c in S:
8            if c == 'I':
9                ans.append(min)
10                min += 1
11            else:
12                ans.append(max)
13                max -= 1
14        ans.append(min)
15        return ans

Java Solution

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

JavaScript Solution

1
2javascript
3var diStringMatch = function(S) {
4    let min = 0, max = S.length;
5    let res = [];
6    
7    for (let i = 0; i < S.length; i++) {
8        if (S[i] === 'I') {
9            res.push(min++);
10        } else {
11            res.push(max--);
12        }
13    }
14    
15    res.push(min);
16    return res;
17};

C++ Solution

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

C# Solution

1
2csharp
3public class Solution {
4    public int[] DiStringMatch(string S) {
5        int min = 0, max = S.Length;
6        int[] result = new int[S.Length + 1];
7            
8        for (int i = 0; i < S.Length; i++) {
9            if (S[i] == 'I') {
10                result[i] = min++;
11            } else {
12                result[i] = max--;
13            }
14        }
15        result[S.Length] = min;
16        return result;
17    }
18}

After analyzing the problem and the presented solutions, we can see that the solution's idea is the same across all the languages: Python, Java, JavaScript, C++, and C#.

Regardless of the language, we initialize two pointers min and max to 0 and the length of the string S which is N respectively. These two pointers represent the smallest and the greatest number yet to be used in forming the output list.

Then, we iterate over the characters of the string S. If at ith index, the character is 'I', we add min to the result and increment it because a smaller number is used and for the next 'I', a bigger number is needed. Similarly, if the character is 'D', we add max to the result and decrement it because a greater number is used and for the next 'D', a smaller number must be used.

Finally, since the result array is supposed to be N+1 long, we append our remaining min into the array since both pointers meet at the same value and represents the last unused number.

In conclusion, the provided solutions handle the problem well and they scale as the length of the input increases. This is because their time complexity is linear, O(N), due to the single loop that is going through each character of the input string.

Therefore, there is no requirement for improvements or additional solutions in this case. Regardless of the implementation language, the critical idea is to properly implement the greedy algorithm explained, and all the given solutions have done so.

Understanding the structure and logic of this solution will allow you to implement it in any other language not covered above, such as PHP, Ruby, Go, Rust, Swift, or Kotlin.