Scale Engineer

DI String Match

Easy
#0896Time: O((n+1)!) in the worst case. Although pruning reduces the search space compared to brute-force, the complexity remains exponential.Space: O(n) for the recursion stack depth and the `used` array.
Patterns
Two PointersGreedy
Data structures
ArrayString

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach builds the permutation step-by-step, from left to right. At each position, it tries to place an unused number that satisfies the current 'I' or 'D' constraint. If it hits a dead end, it backtracks and tries a different number.

Algorithm

  • Initialize an empty permutation perm of size n+1 and a boolean array used of size n+1 to track used numbers.
  • Define a recursive function backtrack(k, perm, used).
  • Base Case: If k == n + 1, a valid permutation has been found. Return true.
  • Recursive Step: Iterate num from 0 to n.
    • If used[num] is false:
      • If k > 0, check the constraint with s[k-1]:
        • If s[k-1] == 'I' and perm[k-1] >= num, this choice is invalid. Continue to the next num.
        • If s[k-1] == 'D' and perm[k-1] <= num, this choice is invalid. Continue to the next num.
      • Place the number: perm[k] = num, used[num] = true.
      • Make a recursive call: if (backtrack(k + 1, perm, used)) return true;.
      • Backtrack: used[num] = false.
  • If the loop finishes without finding a solution, return false.
  • Start the process by calling backtrack(0, perm, used).

Walkthrough

We define a recursive function, say solve(index, current_perm, used_numbers). The function tries to fill current_perm[index]. The base case for the recursion is when index reaches n+1, which means we have successfully constructed a full permutation. In the recursive step, we iterate through all numbers from 0 to n. For each number num, if it has not been used yet, we check if placing it at current_perm[index] is valid by checking against current_perm[index-1] and s[index-1]. If it's valid, we place the number, mark it as used, and make a recursive call for solve(index + 1, ...). If the recursive call fails, we backtrack by undoing the choice and trying the next available number.

class Solution {    public int[] diStringMatch(String s) {        int n = s.length();        int[] perm = new int[n + 1];        boolean[] used = new boolean[n + 1];        backtrack(0, perm, used, s);        return perm;    }     private boolean backtrack(int k, int[] perm, boolean[] used, String s) {        int n = s.length();        if (k == n + 1) {            return true; // Found a valid permutation        }         for (int num = 0; num <= n; num++) {            if (!used[num]) {                if (k > 0) {                    if (s.charAt(k - 1) == 'I' && perm[k - 1] >= num) {                        continue;                    }                    if (s.charAt(k - 1) == 'D' && perm[k - 1] <= num) {                        continue;                    }                }                                perm[k] = num;                used[num] = true;                if (backtrack(k + 1, perm, used, s)) {                    return true;                }                used[num] = false; // Backtrack            }        }        return false;    }}

Complexity

Time

O((n+1)!) in the worst case. Although pruning reduces the search space compared to brute-force, the complexity remains exponential.

Space

O(n) for the recursion stack depth and the `used` array.

Trade-offs

Pros

  • More efficient than brute-force as it prunes invalid branches of the search tree early.

  • It's a general strategy for solving constraint satisfaction problems.

Cons

  • Still too slow for the problem's constraints as the time complexity is fundamentally factorial/exponential.

  • Can lead to stack overflow for large n due to deep recursion.

Solutions

class Solution {public  int[] diStringMatch(String s) {    int n = s.length();    int low = 0, high = n;    int[] ans = new int[n + 1];    for (int i = 0; i < n; i++) {      if (s.charAt(i) == 'I') {        ans[i] = low++;      } else {        ans[i] = high--;      }    }    ans[n] = low;    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem