942. DI String Match

Problem Description

The problem presents a scenario where we need to construct a permutation of integers from 0 to n based on a given string s of length n. Each character in the string represents a relationship between consecutive numbers in the permutation: 'I' indicates that the precedent integer should be less than the subsequent integer, and 'D' dictates the reverse, meaning the precedent should be greater than the subsequent. Our goal is to construct any valid permutation that satisfies the conditions represented by the string s.

Intuition

To solve this problem, we utilize a two-pointer approach to keep track of the smallest and largest numbers not yet placed in the permutation. Initially, we set low to 0 and high to n, representing the lowest and highest possible values in the permutation. We iterate through the string s, and based on whether the current character is an 'I' or a 'D', we either place the low or high value in the permutation and then update low or high accordingly.

When we encounter an 'I', it indicates that perm[i] should be less than perm[i + 1], so we can safely place the current low value at this position and increment low to the next smallest available number.
When we encounter a 'D', it implies that perm[i] should be greater than perm[i + 1], so we place the current high value at this position and decrement high to the next largest available number.

After processing all characters of the string s, we’re left with only one number—either the current low or high value—both of which are equal at this point. We append this last number to the permutation to complete it.

This approach guarantees that the constructed permutation will fulfill the requirements dictated by the string, and since we exhaust all numbers from 0 to n, it also ensures that the generated permutation is complete and valid.

Learn more about Greedy and Two Pointers patterns.

Solution Approach

The given Python solution employs a greedy algorithm that builds the permutation incrementally. Here is a breakdown of how the solution is implemented:

Initialize two pointers, low starting at 0 and high starting at n. These pointers represent the smallest and largest numbers not yet used in the permutation, respectively.
Create an empty list ans to collect the elements of the permutation.
Loop through each character in the input string s with index i ranging from 0 to n - 1.
- If s[i] is 'I', it means the current element of the permutation (indexed by i) should be less than the next element:
  - Append low to the permutation (ans.append(low)).
  - Increment low to the next smallest unused number (low += 1).
- If s[i] is 'D', it means the current element should be greater than the next:
  - Append high to the permutation (ans.append(high)).
  - Decrement high to the next largest unused number (high -= 1).
After the loop, there will be one number left, which will be equal to both low and high since they should have converged. Append this number to ans.
Return the list ans, which now contains the valid permutation.

The algorithm's correctness is guaranteed because each step conforms to the description stated in the problem: appending low on encountering an 'I' results in the next element being greater, and appending high on encountering a 'D' results in the next element being smaller. By incrementing/decrementing low and high, the algorithm also makes sure that each number from 0 to n is used exactly once as required for a permutation.

This methodology leverages a simple yet effective pattern that uses available information at each step to make an optimal choice without needing to consider future elements. The use of array or list data structures for storing the permutation is a natural fit for the problem since permutations are, by definition, ordered collections of elements.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider an example where n = 3 and s = "ID". The goal is to create a permutation of integers 0 to 3 that satisfies the pattern described by s.

Following the solution approach:

We begin with two pointers, low set to 0 and high set to 3.
We start with an empty permutation list ans.

Now, let's loop through the string s:

For i = 0, the first character of s is 'I', which means that the current element should be less than the next element.
- We append low (which is 0) to ans, now ans = [0].
- We increment low to 1.
For i = 1, the next character is 'D', so the current element should be greater than the next.
- We append high (which is 3) to ans, now ans = [0, 3].
- We decrement high to 2.

At this point, we've exhausted s, but we have one more position in the permutation to fill (the n-th position, considering 0-indexing). Since both low and high point to 2, we append the number 2 to ans. Now, ans = [0, 3, 2].

Finally, we have one remaining number, which is 1. We append it to the end of the permutation ans, resulting in ans = [0, 3, 2, 1]. This is a valid permutation that satisfies the condition 'ID': 0 is less than 3 (I), and 3 is greater than 2 (D).

The final permutation ans = [0, 3, 2, 1] is a valid result, guaranteeing the satisfaction of 'I' and 'D' constraints placed by string s.

Solution Implementation

1from typing import List
2
3class Solution:
4    def diStringMatch(self, S: str) -> List[int]:
5        # Determine the length of the given string S
6        n = len(S)
7      
8        # Initialize two pointers, one starting at 0 (low) and one starting at n (high)
9        low, high = 0, n
10      
11        # Create an empty list to store the answer
12        answer = []
13      
14        # Loop through each character in the string
15        for char in S:
16            # If the current character is 'I', append the current low value to answer
17            # and increment low
18            if char == 'I':
19                answer.append(low)
20                low += 1
21            # If the current character is 'D', append the current high value to answer
22            # and decrement high
23            else: # char == 'D'
24                answer.append(high)
25                high -= 1
26      
27        # After the loop, there will be one remaining element, which is low (or high)
28        # Append it to the answer list
29        answer.append(low) # at this point, low == high
30      
31        # Return the constructed answer list
32        return answer
33

1class Solution {
2    public int[] diStringMatch(String S) {
3        // Determine the length of the input string
4        int length = S.length();
5
6        // Create variables for the lowest and highest possible values
7        int low = 0, high = length;
8
9        // Initialize the answer array of length input+1 (to include all numbers from 0 to length)
10        int[] answer = new int[length + 1];
11
12        // Loop through each character in the input string
13        for (int i = 0; i < length; i++) {
14            // If the current character is 'I', assign `low` to the current position and increment `low`
15            if (S.charAt(i) == 'I') {
16                answer[i] = low++;
17            } 
18            // If the current character is 'D', assign `high` to the current position and decrement `high`
19            else {
20                answer[i] = high--;
21            }
22        }
23      
24        // After looping through the string, the `low` and `high` should be equal, assign it to the last position
25        answer[length] = low; // It could also be `high` as both will have the same value
26
27        // Return the computed permutation of integers
28        return answer;
29    }
30}
31

1#include <vector>
2#include <string>
3
4class Solution {
5public:
6    // Function to generate permutations according to the DI string pattern
7    std::vector<int> diStringMatch(std::string str) {
8        int length = str.size(); // Get the size of the input string
9        int low = 0; // Initialize the lowest possible value
10        int high = length; // Initialize the highest possible value
11        std::vector<int> result(length + 1); // Initialize the result vector with size length + 1
12
13        // Iterate through each character in the input string
14        for (int i = 0; i < length; ++i) {
15            // If the current character is 'I', assign the lowest available number and increment 'low'
16            if (str[i] == 'I') {
17                result[i] = low++;
18            } else { // If the current character is not 'I' (thus 'D'), assign the highest available number and decrement 'high'
19                result[i] = high--;
20            }
21        }
22
23        // Since each 'D' and 'I' in the string consumed a number (low or high), the last number left is 'low'
24        result[length] = low; // Assign the last element, which will be equal to 'low' (or 'high' since they now should be the same)
25
26        return result; // Return the resulting permutation vector
27    }
28};
29

1function diStringMatch(s: string): number[] {
2    // The length of the input string
3    const length = s.length;
4    // Resultant array which will hold the permutation of length+1 elements
5    const result = new Array(length + 1);
6    // Initialize pointers for the lowest and highest possible values
7    let low = 0;
8    let high = length;
9  
10    // Iterate over the string characters
11    for (let i = 0; i < length; i++) {
12        // If the current character is 'I', assign the lowest value and increase it
13        if (s[i] === 'I') {
14            result[i] = low++;
15        // If the current character is not 'I' (hence 'D'), assign the highest value and decrease it
16        } else {
17            result[i] = high--;
18        }
19    }
20  
21    // Assign the last element in the result array,
22    // which is either the increased low or the decreased high (after the loop, they are equal)
23    result[length] = low;
24    // Return the resulting permutation array
25    return result;
26}
27

Time and Space Complexity

The code defines a function diStringMatch that takes a string s and generates a permutation of integers from 0 to len(s) such that adjacent elements correspond to 'I' (increase) and 'D' (decrease) in the string s.

Time Complexity

The function consists of a single loop that iterates over the string s exactly once, with a constant number of operations performed during each iteration. The number of iterations is equal to n where n is the length of the string s. After the loop, one additional element is appended to the ans list. However, this does not change the overall time complexity. Therefore, the time complexity of the function is O(n).

Space Complexity

The function uses extra space in the form of the list ans which will contain n + 1 elements by the end of the function's execution, as every character in the string s corresponds to an element being added to the list, with one final element being added after the loop completes. Thus, the space complexity of the function is also O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know