DI String Match

Problem Statement

In this task, we are given a string s of length n, which consists of characters 'I' (Increasing) and 'D' (Decreasing). Each character in s describes the relationship between consecutive elements in a permutation perm of the integers within the range [0, n]. Specifically:

• s[i] == 'I' implies that perm[i] < perm[i + 1].
• s[i] == 'D' implies that perm[i] > perm[i + 1].

Our goal is to construct any valid permutation perm that fits the description indicated by the string s. It's important to note that multiple valid permutations can exist for the same string s. We simply need to return one of those permutations.

Examples

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

Approach and Intuition

The approach to generating a valid permutation from the string s uses a straightforward greedy technique, utilizing two pointers to represent the smallest and largest numbers available to construct perm.

1. Initialize the permutation array perm of size n+1 to store the result.
2. Use two pointers, low and high. Set low to 0 and high to n.
3. Traverse through the string s:
   • If s[i] == 'I', set perm[i] to low and increment low. This uses the smallest available number and ensures the next number is higher.
   • If s[i] == 'D', set perm[i] to high and decrement high. This uses the largest available number, guaranteeing the next number is smaller.
4. After processing all characters in s, set perm[n] to the remaining value of low (which now equals high).
5. This method efficiently constructs the permutation by picking the extreme available values based on the immediate requirement (either smallest or largest), ensuring the conditions perm[i] < perm[i + 1] or perm[i] > perm[i + 1] are satisfied.

By this approach, the permutation is built in a linear pass based on the relationship flags provided in s, efficiently and correctly forming a permutation that meets the criteria.

Solutions

class Solution {
public:
    vector<int> diStringMatch(string pattern) {
        int length = pattern.size();
        int minVal = 0, maxVal = length;
        vector<int> result(length + 1);
    
        for (int i = 0; i < length; ++i) {
            if (pattern[i] == 'I') {
                result[i] = minVal++;
            } else {
                result[i] = maxVal--;
            }
        }
    
        result[length] = minVal;
        return result;
    }
};