Algorithm

Problem Name: 942. DI String Match

Problem Link: https://leetcode.com/problems/di-string-match/
 

A permutation perm of n + 1 integers of all the integers in the range [0, n] can be represented as a string s of length n where:

  • s[i] == 'I' if perm[i] < perm[i + 1], and
  • s[i] == 'D' if perm[i] > perm[i + 1].

Given a string s, reconstruct the permutation perm and return it. If there are multiple valid permutations perm, return any of them.

 

Example 1:

Input: s = "IDID"
Output: [0,4,1,3,2]

Example 2:

Input: s = "III"
Output: [0,1,2,3]

Example 3:

Input: s = "DDI"
Output: [3,2,0,1]

 

Constraints:

  • 1 <= s.length <= 105
  • s[i] is either 'I' or 'D'.

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


class Solution {
  public int[] diStringMatch(String S) {
    int n = S.length();
    int low = 0;
    int high = n;
    int[] ans = new int[n + 1];
    for (int i = 0; i  <  n; i++) {
      ans[i] = S.charAt(i) == 'I' ? low++ : high--;
    }
    ans[n] = low;
    return ans;
  }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
s = "IDID"

Output

x
–
+
cmd
[0,4,1,3,2]

#2 Code Example with Javascript Programming

Code - Javascript Programming


const diStringMatch = function(S) {
  const N = S.length
  const arr = []
  for(let i = 0; i  < = N; i++) {
    arr[i] = i
  }
  const res = []
  for(let i = 0; i  <  N; i++) {
    if(S[i] === 'I') {
      res.push(arr.shift())
    } else if(S[i] === 'D') {
      res.push(arr.pop())
    }
  }
  res.push(arr.pop())
  return res
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
s = "IDID"

Output

x
–
+
cmd
[0,4,1,3,2]

#3 Code Example with Python Programming

Code - Python Programming


class Solution:
    def diStringMatch(self, S):
        l, r, arr = 0, len(S), []
        for s in S:
            arr.append(l if s == "I" else r)
            l, r = l + (s == "I"), r - (s == "D")
        return arr + [l]
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
s = "III"

Output

x
–
+
cmd
[0,1,2,3]

#4 Code Example with C# Programming

Code - C# Programming


namespace LeetCode
{
    public class _0942_DIStringMatch
    {
        public int[] DiStringMatch(string S)
        {
            var result = new int[S.Length + 1];
            int lo = 0, hi = S.Length;
            for (int i = 0; i  <  S.Length; i++)
            {
                if (S[i] == 'I') result[i] = lo++;
                else if (S[i] == 'D') result[i] = hi--;
            }

            result[S.Length] = lo;
            return result;
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
s = "III"

Output

x
–
+
cmd
[0,1,2,3]
Advertisements

Demonstration

Previous
#941 Leetcode Valid Mountain Array Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#943 Leetcode Find the Shortest Superstring Solution in C, C++, Java, JavaScript, Python, C# Leetcode