DI String Match

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

1class Solution {2    public int[] diStringMatch(String s) {3        int n = s.length();4        int[] perm = new int[n + 1];5        boolean[] used = new boolean[n + 1];6        backtrack(0, perm, used, s);7        return perm;8    }9 10    private boolean backtrack(int k, int[] perm, boolean[] used, String s) {11        int n = s.length();12        if (k == n + 1) {13            return true; // Found a valid permutation14        }15 16        for (int num = 0; num <= n; num++) {17            if (!used[num]) {18                if (k > 0) {19                    if (s.charAt(k - 1) == 'I' && perm[k - 1] >= num) {20                        continue;21                    }22                    if (s.charAt(k - 1) == 'D' && perm[k - 1] <= num) {23                        continue;24                    }25                }26                27                perm[k] = num;28                used[num] = true;29                if (backtrack(k + 1, perm, used, s)) {30                    return true;31                }32                used[num] = false; // Backtrack33            }34        }35        return false;36    }37}

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

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.

1class Solution {2    public int[] diStringMatch(String s) {3        int n = s.length();4        int[] perm = new int[n + 1];5        for (int i = 0; i <= n; i++) {6            perm[i] = i;7        }8 9        // This do-while loop with nextPermutation generates all permutations10        do {11            if (isValid(perm, s)) {12                return perm;13            }14        } while (nextPermutation(perm));15 16        return new int[0]; // Should not be reached17    }18 19    private boolean isValid(int[] perm, String s) {20        for (int i = 0; i < s.length(); i++) {21            if (s.charAt(i) == 'I' && perm[i] >= perm[i + 1]) {22                return false;23            }24            if (s.charAt(i) == 'D' && perm[i] <= perm[i + 1]) {25                return false;26            }27        }28        return true;29    }30 31    // A standard implementation of the next permutation algorithm32    private boolean nextPermutation(int[] nums) {33        int i = nums.length - 2;34        while (i >= 0 && nums[i] >= nums[i + 1]) {35            i--;36        }37        if (i < 0) {38            return false;39        }40        int j = nums.length - 1;41        while (nums[j] <= nums[i]) {42            j--;43        }44        swap(nums, i, j);45        reverse(nums, i + 1);46        return true;47    }48 49    private void swap(int[] nums, int i, int j) {50        int temp = nums[i];51        nums[i] = nums[j];52        nums[j] = temp;53    }54 55    private void reverse(int[] nums, int start) {56        int i = start, j = nums.length - 1;57        while (i < j) {58            swap(nums, i, j);59            i++;60            j--;61        }62    }63}

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

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

1class Solution {2    public int[] diStringMatch(String s) {3        int n = s.length();4        int[] perm = new int[n + 1];5        int low = 0;6        int high = n;7 8        for (int i = 0; i < n; i++) {9            if (s.charAt(i) == 'I') {10                perm[i] = low++;11            } else { // s.charAt(i) == 'D'12                perm[i] = high--;13            }14        }15        16        // The last element will be the only number left.17        // At this point, low == high.18        perm[n] = low; 19        20        return perm;21    }22}