# DI String Match
**Difficulty:** EASY
[External](https://leetcode.com/problems/di-string-match)
Canonical: https://scaleengineer.com/dsa/problems/di-string-match
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, String
---
## Problem
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
## Brute-Force by Generating All Permutations
This approach involves generating every possible permutation of the numbers from `0` to `n`. For each permutation, we check if it satisfies the conditions given by the input string `s`. The first permutation that satisfies the conditions is returned.
**Time:** O(n * (n+1)!). There are `(n+1)!` permutations of `n+1` elements. For each permutation, we perform a check that takes `O(n)` time. · **Space:** O(n) for storing the permutation. The recursion stack for generating permutations can also go up to O(n).
**Pros:** Conceptually simple to understand as it directly translates the problem definition.; Guaranteed to find a solution since one is guaranteed to exist.
**Cons:** Extremely inefficient due to its factorial time complexity.; Will cause a 'Time Limit Exceeded' error for even moderately small inputs (e.g., n > 10), making it impractical for the given constraints.
### Explanation
The algorithm first needs a way to generate all permutations of numbers `[0, 1, ..., n]`. This can be done using a standard algorithm like Heap's algorithm or by using recursion and backtracking. For each generated permutation `perm`, we construct a temporary string based on `perm`. For each `i` from `0` to `n-1`, if `perm[i] < perm[i+1]`, we would expect an 'I'; otherwise, we'd expect a 'D'. We compare this expectation with the input string `s`. If they match for all positions, we have found a valid permutation, and we can return it. Since the problem guarantees that a solution exists, this process will eventually find one.

```java
class Solution {
    public int[] diStringMatch(String s) {
        int n = s.length();
        int[] perm = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            perm[i] = i;
        }

        // This do-while loop with nextPermutation generates all permutations
        do {
            if (isValid(perm, s)) {
                return perm;
            }
        } while (nextPermutation(perm));

        return new int[0]; // Should not be reached
    }

    private boolean isValid(int[] perm, String s) {
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'I' && perm[i] >= perm[i + 1]) {
                return false;
            }
            if (s.charAt(i) == 'D' && perm[i] <= perm[i + 1]) {
                return false;
            }
        }
        return true;
    }

    // A standard implementation of the next permutation algorithm
    private boolean nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i < 0) {
            return false;
        }
        int j = nums.length - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }
        swap(nums, i, j);
        reverse(nums, i + 1);
        return true;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
}
```
### Algorithm
*   Let `n` be the length of the input string `s`.
*   Generate all permutations of the integers `[0, 1, ..., n]`.
*   For each permutation `p`:
    *   Check if `p` is a valid DI string match.
    *   To check, iterate from `i = 0` to `n-1`:
        *   If `s[i] == 'I'` and `p[i] > p[i+1]`, `p` is not a match. Break and check the next permutation.
        *   If `s[i] == 'D'` and `p[i] < p[i+1]`, `p` is not a match. Break and check the next permutation.
    *   If the loop completes without breaking, `p` is a valid match. Return `p`.

## 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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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)`.

## Greedy Two-Pointer Approach
This is a highly efficient, linear-time approach. The key insight is that to satisfy an 'I' (increase) condition, we should pick the smallest available number to leave maximum room for future larger numbers. Conversely, for a 'D' (decrease) condition, we should pick the largest available number to leave room for smaller numbers.
**Time:** O(n), where n is the length of the string `s`. We iterate through the string once. · **Space:** O(n) or O(1) auxiliary space. We need `O(n)` space for the output array `perm`. If the output array is not considered auxiliary space, the space complexity is `O(1)`.
**Pros:** Optimal time complexity, solving the problem in a single pass.; Optimal space complexity, using constant extra space (if the output array is not counted).; Simple to implement and understand once the greedy logic is clear.
**Cons:** The greedy choice might not be immediately obvious without some thought and analysis.
### Explanation
We maintain two pointers, `low` and `high`, initialized to `0` and `n` respectively. These pointers represent the smallest and largest numbers currently available from the range `[0, n]`. We iterate through the input string `s` from `i = 0` to `n-1`, building the permutation `perm` from left to right. For each character `s[i]`, if it's 'I', we greedily choose the smallest available number (`low`) for `perm[i]` and increment `low`. This ensures that any subsequent number chosen will be greater. If `s[i]` is 'D', we greedily choose the largest available number (`high`) for `perm[i]` and decrement `high`, ensuring any subsequent number will be smaller. After the loop, exactly one number remains, and `low` will be equal to `high`. This last number is placed at `perm[n]`.

```java
class Solution {
    public int[] diStringMatch(String s) {
        int n = s.length();
        int[] perm = new int[n + 1];
        int low = 0;
        int high = n;

        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'I') {
                perm[i] = low++;
            } else { // s.charAt(i) == 'D'
                perm[i] = high--;
            }
        }
        
        // The last element will be the only number left.
        // At this point, low == high.
        perm[n] = low; 
        
        return perm;
    }
}
```
### Algorithm
*   Let `n` be the length of `s`.
*   Initialize `low = 0` and `high = n`.
*   Initialize an result array `perm` of size `n+1`.
*   Iterate `i` from `0` to `n-1`:
    *   If `s.charAt(i) == 'I'`:
        *   Set `perm[i] = low`.
        *   Increment `low`.
    *   Else (`s.charAt(i) == 'D'`):
        *   Set `perm[i] = high`.
        *   Decrement `high`.
*   After the loop, one position in `perm` is left to be filled (`perm[n]`) and `low` will equal `high`.
*   Set `perm[n] = low` (or `high`).
*   Return `perm`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> diStringMatch(string s) {
    int n = s.size();
    int low = 0, high = n;
    vector<int> ans(n + 1);
    for (int i = 0; i < n; ++i) {
      if (s[i] == 'I') {
        ans[i] = low++;
      } else {
        ans[i] = high--;
      }
    }
    ans[n] = low;
    return ans;
  }
};

```

### Python

```python
class Solution:
    def diStringMatch(self, s: str) -> List[int]: n = len(s) low, high = 0, n ans = [] for i in range(n): if s[i] == 'I': ans . append(low) low += 1 else: ans . append(high) high -= 1 ans . append(low) return ans

```