Leetcode 942. DI String Match
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
i
th character inS
is'I'
, the element at thei
th index of the array is less than the element at the(i+1)
th index of the array - When the
i
th character inS
is'D'
, the element at thei
th 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 i
th 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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.