
Problem Statement
In permutations, the order in which elements appear is crucial. Given a string s
that represents a sequence of 'I' (increasing) and 'D' (decreasing) conditions between consecutive elements of a permutation perm
, the task is to construct the lexicographically smallest permutation of integers from 1 to n
, where n
is the length of s
plus 1. Each 'I' in the string denotes the subsequent number being greater than the previous, while each 'D' indicates it being smaller. Utilizing this pattern, we are to generate and return the smallest sequence possible that fits the conditions given by s
.
Examples
Example 1
Input:
s = "I"
Output:
[1,2]
Explanation:
[1,2] is the only legal permutation that can represented by s, where the number 1 and 2 construct an increasing relationship.
Example 2
Input:
s = "DI"
Output:
[2,1,3]
Explanation:
Both [2,1,3] and [3,1,2] can be represented as "DI", but since we want to find the smallest lexicographical permutation, you should return [2,1,3]
Constraints
1 <= s.length <= 105
s[i]
is either'I'
or'D'
.
Approach and Intuition
- Initialize an empty list
perm
to store the permutation and a listavailable
containing the numbers from 1 ton
(inclusive). This list helps in directly appending the smallest or largest available number as required by the sequence ins
. - Iterate through each character in
s
:- If the current character is 'I' (indicating an increase):
- Append the smallest available number from
available
toperm
.
- Append the smallest available number from
- If the current character is 'D' (indicating a decrease):
- Append the largest available number from
available
toperm
.
- Append the largest available number from
- If the current character is 'I' (indicating an increase):
- After processing all characters in
s
, append the last remaining number inavailable
toperm
as the sequence ins
leaves one last number placement to be decided by the remaining unused number. - This approach guarantees the lexicographically smallest permutation, since at every decision point, the algorithm places the smallest (or largest, when decreasing) possible value from the remaining values, adhering strictly to the pattern imposed by
s
. Using this systematic approach provides clarity on how the sequence should build up and helps direct choices that satisfy both the pattern and lexicographical conditions.
Solutions
- Java
public class Solution {
public int[] generatePermutation(String sequence) {
int length = sequence.length() + 1;
int[] output = new int[length];
output[0] = 1;
int counter = 1;
while (counter <= sequence.length()) {
output[counter] = counter + 1;
int start = counter;
if (sequence.charAt(counter - 1) == 'D') {
while (counter <= sequence.length() && sequence.charAt(counter - 1) == 'D') {
counter++;
}
for (int place = start - 1, value = counter; place <= counter - 1; place++, value--) {
output[place] = value;
}
} else {
counter++;
}
}
return output;
}
}
The provided Java code defines a method named generatePermutation
in a class called Solution
. This method takes a string sequence
containing a series of characters ('D' or 'I') as input and generates a permutation of integers. Each character in the sequence represents a directive for the permutation:
- 'D' indicates that the next number in the output array should be in decreasing order.
- 'I' indicates an increasing order relative to the previous number.
Here is a concise step-by-step explanation of how the method functions:
- Initialize an integer array
output
with a size one greater than the length of the input sequence. This accommodates the sequence plus an additional integer. - Set the first element of
output
to 1. - Use a counter initialized to 1 to iterate over the characters of the sequence.
- For each 'D' encountered in the sequence, find the extent of the sequence of 'D's and populate the
output
array with decremented values starting from the next expected number after the last sequence processed. - If an 'I' is found, simply increment the counter and continue, as the array already has the numbers in increasing order from this operation.
- Return the
output
array.
This method smartly forms a permutation where the order of digits changes between increasing and decreasing based on the character found in the provided sequence. This achieves the desired arrangement without sorting operations, thus directly constructing the output array in an efficient manner based on the input instructions.
No comments yet.