DI String Match

EASY

Description

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 <= 10⁵
s[i] is either 'I' or 'D'.

Approaches

Checkout 3 different approaches to solve DI String Match. Click on different approaches to view the approach and algorithm in detail.

Backtracking Search

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

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 Analysis

Time Complexity: O((n+1)!) in the worst case. Although pruning reduces the search space compared to brute-force, the complexity remains exponential.Space Complexity: O(n) for the recursion stack depth and the `used` array.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for DI String Match. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for DI String Match

Patterns:

Two PointersGreedy

Data Structures:

ArrayString