484. Find Permutation
Problem Description
In this LeetCode problem, we are given a string s
that represents a sequence of I
(increase) and D
(decrease) operations. This string s
maps to a permutation perm
of length n + 1
, where n
is the length of s
. The characters in the string s
determine whether the consecutive numbers in the permutation perm
are in increasing (I
) or decreasing (D
) order.
Our goal is to reconstruct the permutation perm
from the given sequence s
such that the permutation is the lexicographically smallest possible. Lexicographically smallest means that if we treat each permutation as a number, we want the smallest possible number that can be formed while still satisfying the pattern of I
and D
from the string s
.
For example, if the string s
is IID
, then a possible permutation that fits the pattern is 12345
where perm[0] < perm[1]
, perm[1] < perm[2]
and perm[3] > perm[4]
. However, 12345
may not be the lexicographically smallest permutation, and our task is to find the smallest one.
Intuition
The intuition behind the solution comes from the fact that we want to make the permutation as small as possible from left to right. This means that whenever we encounter an I
in the string s
, we should choose the smallest available number at that point to keep the permutation small. Conversely, when we encounter a D
, we want to defer choosing the numbers until we reach the end of the consecutive sequence of D
s, and then fill in the numbers in reverse. By doing so, we ensure that the number before the D
sequence is greater than the numbers after it, while still keeping those numbers as small as possible.
The process to arrive at this solution involves the following steps:
-
Fill in the array
ans
with the numbers from1
ton+1
in ascending order. Assuming initially that all the following characters are 'I', this would be the lexicographically smallest permutation. -
Traverse the string
s
and when we see aD
, identify the consecutive sequence ofD
s. We note where this sequence ends. -
Reverse the sub-array
ans[i : j + 1]
wherei
is the start of theD
sequence, andj
is the index of the lastD
in the sequence. This places the larger numbers before the smaller numbers, which is required by theD
sequence. -
Continue this process until we have gone through the entire string
s
.
By following these steps, we construct the lexicographically smallest permutation that satisfies the given sequence s
.
Solution Approach
The implementation of the solution follows the intuition closely, using mostly basic data structures and control flow patterns available in Python.
Here’s a step-by-step breakdown of the algorithm implemented by the Solution class:
-
Initialize a list called
ans
that contains the numbers from1
ton + 1
(inclusive). Because the sequence must contain each number from1
ton + 1
exactly once, this fills in the default ascending order for the "I" scenario. -
Create a pointer
i
that will traverse the strings
from the beginning. -
While
i
is less than the length of the strings
, look for consecutive "D"s. This is achieved by initializing another pointerj
toi
, which moves forward as long as it finds "D". -
For each sequence of "D"s, reverse the corresponding subsequence in
ans
. The sliceans[i : j + 1]
represents the numbers that need to be in descending order to satisfy this sequence of "D"s. By reversing using the[::-1]
slice, we arrange them correctly while keeping them as small as possible. -
Update the pointer
i
to continue from the end of the handled "D" sequence. Themax(i + 1, j)
ensures that ifj
has not moved (indicating that there were no "D"s),i
continues to the next character. Ifj
has moved,i
skips over the "D" sequence. -
After the completion of the loop,
ans
now represents the lexicographically smallest permutation in accordance with the pattern given bys
.
This algorithm leverages Python's list indexing and slicing capabilities to reverse subarrays efficiently. The in-place reversal of subarrays helps to maintain the overall lexicographic order by ensuring that the smallest values are placed after sequences of "D"s.
Once the list ans
has been fully traversed and modified, it is returned as the lexicographically smallest permutation that follows the increase-decrease pattern dictated by string s
. By using this straightforward implementation, there is no need for complex data structures or additional space beyond the initial list to store the permutation. The in-place operations ensure that the space complexity stays constrained to O(n), where n is the number of elements in perm
.
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 illustrate the solution approach with a simple example where the string s
is DID
.
-
First, we need to initialize a list
ans
that contains numbers from1
ton + 1
. Since the length ofs
is 3,n + 1
equals 4. Therefore, we initializeans
to[1, 2, 3, 4]
. -
We then create a pointer
i
starting at the beginning of the strings
. Initially,i = 0
. -
Now we start traversing the string
s
. Ats[0]
, we haveD
, which signifies thatans[0]
should be greater thanans[1]
. We find the next sequence of "I" or the end of the string to determine the range to reverse. In this case, the next character ats[1]
isI
, signaling the end of ourD
sequence. So, we have aD
sequence fromi = 0
toj = 0
. -
We reverse
ans[i : j + 1]
, but in this case, sincei
andj
are the same, the list remains[1, 2, 3, 4]
. -
We move to the next character in the string
s
and incrementi
tomax(i + 1, j)
, which makesi = 1
. -
At
s[1]
, we haveI
, so we leaveans
as it is because the permutation should remain in ascending order forI
. -
We move
i
to2
because there was noD
sequence. -
At
s[2]
, we haveD
again, so we look for the nextI
or the end of the string. The end of the string comes next, so ourD
sequence is fromi = 2
toj = 2
. -
We reverse
ans[i : j + 1]
, which means reversing the slice[3, 4]
. After the reversal,ans
becomes[1, 2, 4, 3]
. -
Iteration is complete as we reach the end of
s
.
Now, the list ans
represents [1, 2, 4, 3]
, which is the lexicographically smallest permutation following the DID
pattern of the string s
. Here’s a step by step representation of ans
after each iteration:
- Initial
ans
:[1, 2, 3, 4]
- After handling
D
ats[0]
:[1, 2, 3, 4]
(no change since it's a singleD
) - After handling
I
ats[1]
:[1, 2, 3, 4]
(no change sinceans
is already ascending) - After handling
D
ats[2]
:[1, 2, 4, 3]
(the last two numbers are reversed)
The final result is the permutation [1, 2, 4, 3]
, which satisfies the original pattern and is lexicographically the smallest possible.
Solution Implementation
1from typing import List
2
3class Solution:
4 def findPermutation(self, s: str) -> List[int]:
5 # Length of the input pattern
6 pattern_length = len(s)
7
8 # Create an initial list of integers from 1 to n+1
9 # For the pattern 'DI', the initial list will be [1, 2, 3]
10 permutation = list(range(1, pattern_length + 2))
11
12 # Start iterating over the pattern
13 index = 0
14 while index < pattern_length:
15 # Find the end of the current 'D' sequence
16 sequence_end = index
17 while sequence_end < pattern_length and s[sequence_end] == 'D':
18 sequence_end += 1
19
20 # Reverse the sub-list corresponding to the 'D' sequence found
21 # This is done because numbers must be in descending order for 'D'
22 permutation[index : sequence_end + 1] = permutation[index : sequence_end + 1][::-1]
23
24 # Move to next starting point, one past this 'D' sequence or increment by one
25 index = max(index + 1, sequence_end)
26
27 # Return the modified list as the resulting permutation
28 return permutation
29
30# Example usage:
31# solution = Solution()
32# print(solution.findPermutation("DID"))
33
1class Solution {
2
3 // This function produces the permutation of numbers based on the given pattern string.
4 public int[] findPermutation(String pattern) {
5 int length = pattern.length();
6 int[] result = new int[length + 1];
7
8 // Initialize the result array with natural numbers starting from 1 to n+1
9 for (int i = 0; i <= length; ++i) {
10 result[i] = i + 1;
11 }
12
13 int index = 0;
14 // Traverse through the pattern string
15 while (index < length) {
16 int startIndex = index;
17 // Find the contiguous sequence of 'D's
18 while (startIndex < length && pattern.charAt(startIndex) == 'D') {
19 startIndex++;
20 }
21 // Reverse the sequence to fulfill the 'D' requirement in permutation
22 reverse(result, index, startIndex);
23 // Advance the index to the position after the reversed section or move it at least one step forward.
24 index = Math.max(index + 1, startIndex);
25 }
26
27 return result;
28 }
29
30 // This function reverses the elements in the array between indices i and j.
31 private void reverse(int[] array, int start, int end) {
32 // Note end is decremented to swap the elements inclusively
33 for (int left = start, right = end - 1; left < right; ++left, --right) {
34 // Swap elements at indices left and right
35 int temp = array[left];
36 array[left] = array[right];
37 array[right] = temp;
38 }
39 }
40}
41
1#include <vector>
2#include <algorithm>
3#include <numeric>
4
5class Solution {
6public:
7 // Method to find the permutation according to the input sequence.
8 vector<int> findPermutation(string sequence) {
9 int n = sequence.size(); // Size of the input string
10 // Create a vector to store the answer, initializing
11 // it with an increasing sequence from 1 to n+1.
12 vector<int> permutation(n + 1);
13 iota(permutation.begin(), permutation.end(), 1);
14
15 int currentIndex = 0; // Start from the beginning of the string.
16 // Iterate through the entire sequence.
17 while (currentIndex < n) {
18 int nextIndex = currentIndex;
19 // Find the sequence of 'D's in the input string.
20 while (nextIndex < n && sequence[nextIndex] == 'D') {
21 ++nextIndex; // Move to the next index if it's a 'D'.
22 }
23 // Reverse the subvector from the start of 'D's to just past the last 'D'.
24 reverse(permutation.begin() + currentIndex, permutation.begin() + nextIndex + 1);
25 // Move to the index after the sequence of 'D's or increment by one if no 'D's were found.
26 currentIndex = max(currentIndex + 1, nextIndex);
27 }
28
29 return permutation; // Return the resulting permutation.
30 }
31};
32
1// Helper function to generate an increasing sequence array from 1 to n
2function iota(n: number): number[] {
3 return Array.from({ length: n }, (_, index) => index + 1);
4}
5
6// Helper function to reverse a subarray from start to end indices
7function reverse(array: number[], start: number, end: number): void {
8 while (start < end) {
9 [array[start], array[end]] = [array[end], array[start]]; // swap elements
10 start++;
11 end--;
12 }
13}
14
15// Function to find the permutation as per the input sequence
16function findPermutation(sequence: string): number[] {
17 const n = sequence.length; // Get the size of the input sequence
18 // Initialize the permutation array as an increasing sequence from 1 to n+1
19 let permutation = iota(n + 1);
20
21 let currentIndex = 0; // Start from the beginning of the sequence
22
23 // Iterate through the entire sequence
24 while (currentIndex < n) {
25 let nextIndex = currentIndex;
26 // Find the sequence of 'D's in the input string
27 while (nextIndex < n && sequence[nextIndex] === 'D') {
28 nextIndex++; // Advance to the next index if it's a 'D'
29 }
30 // Reverse the subarray from the start of 'D's to just past the last 'D'
31 reverse(permutation, currentIndex, nextIndex);
32 // Move to the index after the sequence of 'D's or increment by one if no 'D's were found
33 currentIndex = Math.max(currentIndex + 1, nextIndex);
34 }
35
36 return permutation; // Return the resulting permutation
37}
38
Time and Space Complexity
Time Complexity
The time complexity of the code snippet is O(n)
, where n
is the length of the input string s
. This is because the code involves iterating over each character in the input string up to twice. The while loop iterates over each character, and within this loop, there is another while loop that continues as long as the character is 'D'
. However, the inner loop advances the index j
every time it finds a 'D'
, thereby skipping that section for the outer loop. Therefore, even though there is a nested loop, each character will be looked at a constant number of times, resulting in linear time complexity overall.
Additionally, the reversal of the sublist ans[i : j + 1]
takes linear time with respect to the length of the sublist, but since it's done without overlapping with other sublists, the total amount of work for all reversals summed together still does not exceed O(n)
.
Space Complexity
The space complexity is O(n)
because we are storing the result in a list ans
which contains n + 1
elements. No additional significant space is used, and the space used for the output does not count towards extra space complexity when analyzing space complexity. The in-place reversal operation does not incur additional space cost.
Learn more about how to find time and space complexity quickly using problem constraints.
Which technique can we use to find the middle of a linked list?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
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
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
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.