Find Permutation

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

1. Initialize an empty list perm to store the permutation and a list available containing the numbers from 1 to n (inclusive). This list helps in directly appending the smallest or largest available number as required by the sequence in s.
2. Iterate through each character in s:
   • If the current character is 'I' (indicating an increase):
     • Append the smallest available number from available to perm.
   • If the current character is 'D' (indicating a decrease):
     • Append the largest available number from available to perm.
3. After processing all characters in s, append the last remaining number in available to perm as the sequence in s leaves one last number placement to be decided by the remaining unused number.
4. 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

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;
    }
}