Code Implementation

class Solution:
    def diStringMatch(self, s: str) -> list[int]:
        n = len(s)
        low, high = 0, n
        result = []
        for char in s:
            if char == 'I':
                result.append(low)
                low += 1
            else:
                result.append(high)
                high -= 1
        result.append(low)  # low == high here
        return result
      

class Solution {
public:
    vector<int> diStringMatch(string s) {
        int n = s.size();
        int low = 0, high = n;
        vector<int> result;
        for (char c : s) {
            if (c == 'I') {
                result.push_back(low++);
            } else {
                result.push_back(high--);
            }
        }
        result.push_back(low); // low == high
        return result;
    }
};
      

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

var diStringMatch = function(s) {
    let n = s.length;
    let low = 0, high = n;
    let result = [];
    for (let i = 0; i < n; i++) {
        if (s[i] === 'I') {
            result.push(low++);
        } else {
            result.push(high--);
        }
    }
    result.push(low); // low == high
    return result;
};
      

Problem Description

You are given a string s consisting only of the characters 'I' (for "increase") and 'D' (for "decrease"). Your task is to construct a permutation perm of the integers from 0 to n (where n = len(s)) such that:

• If s[i] == 'I', then perm[i] < perm[i+1]
• If s[i] == 'D', then perm[i] > perm[i+1]

Each integer from 0 to n must be used exactly once in perm (no repeats). Only one valid solution is required.

For example, if s = "IDID", a valid output could be [0,4,1,3,2].

Thought Process

At first glance, this problem seems to ask us to generate all possible permutations and check them one by one, but that would be very inefficient, especially since the number of permutations grows rapidly with n. Instead, we want to find a way to directly construct a valid permutation by following the pattern described by s.

Since each character in s tells us whether the next number should be bigger or smaller, we can think about using the smallest and largest available numbers at each step. If we see an 'I', we assign the current smallest unused number; if we see a 'D', we assign the current largest unused number. This way, we always satisfy the required relationship between consecutive elements, and we use up all numbers exactly once.

This approach avoids brute force and leverages a greedy strategy: always make the locally optimal choice (smallest for 'I', largest for 'D') to ensure the global pattern is achieved.

Solution Approach

Let's break down the algorithm step by step:

1. Initialize two pointers: Start with low = 0 and high = n, where n is the length of s. These pointers represent the smallest and largest available numbers, respectively.
2. Iterate through the string s: For each character:
   • If the character is 'I', assign low to the current position in the permutation and increment low by 1.
   • If the character is 'D', assign high to the current position and decrement high by 1.
3. Assign the last number: After the loop, only one number remains (since we started with n+1 numbers for n positions). Both low and high will be equal, so assign this value to the last position in the permutation.
4. Return the result: The constructed list is a valid permutation that matches the input pattern.

This method is efficient because it processes each character in s only once, and it never revisits or reuses numbers.

Example Walkthrough

Let's use the sample input s = "IDID". The numbers available are 0, 1, 2, 3, 4.

1. Step 1: s[0] = 'I' → assign low = 0. Increment low to 1.
   Current permutation: [0]
2. Step 2: s[1] = 'D' → assign high = 4. Decrement high to 3.
   Current permutation: [0, 4]
3. Step 3: s[2] = 'I' → assign low = 1. Increment low to 2.
   Current permutation: [0, 4, 1]
4. Step 4: s[3] = 'D' → assign high = 3. Decrement high to 2.
   Current permutation: [0, 4, 1, 3]
5. Final step: Only low = high = 2 remains. Assign to last position.
   Final permutation: [0, 4, 1, 3, 2]

At each step, the assignment ensures that the 'I' and 'D' requirements are satisfied, and all numbers are used exactly once.

Time and Space Complexity

Brute-force approach: Generating all possible permutations and checking each one would require O((n+1)!) time and space, which is infeasible even for moderate values of n.

Optimized approach (greedy two-pointer):

• Time Complexity: O(n), since we process each character of s exactly once.
• Space Complexity: O(n), for storing the resulting permutation of length n+1.

Summary

The DI String Match problem is elegantly solved using a greedy two-pointer approach. By assigning the smallest available number for 'I' and the largest for 'D', we can construct a valid permutation in linear time. This strategy avoids brute-force permutation generation, ensuring both efficiency and correctness. The key insight is to match the pattern directly with available numbers, making the solution both simple and powerful.