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 thanperm[i + 1]
, so we can safely place the currentlow
value at this position and incrementlow
to the next smallest available number. - When we encounter a 'D', it implies that
perm[i]
should be greater thanperm[i + 1]
, so we place the currenthigh
value at this position and decrementhigh
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 at0
andhigh
starting atn
. 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 indexi
ranging from0
ton - 1
.- If
s[i]
is'I'
, it means the current element of the permutation (indexed byi
) 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
).
- Append
- 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
).
- Append
- If
- After the loop, there will be one number left, which will be equal to both
low
andhigh
since they should have converged. Append this number toans
. - 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 EvaluatorExample 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 to0
andhigh
set to3
. - We start with an empty permutation list
ans
.
Now, let's loop through the string s
:
- For
i = 0
, the first character ofs
is 'I', which means that the current element should be less than the next element.- We append
low
(which is0
) toans
, nowans = [0]
. - We increment
low
to1
.
- We append
- For
i = 1
, the next character is 'D', so the current element should be greater than the next.- We append
high
(which is3
) toans
, nowans = [0, 3]
. - We decrement
high
to2
.
- We append
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.
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?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we