Find Permutation

Updated on 26 May, 2025
Find Permutation header image

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

  • Java
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:

  1. 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.
  2. Set the first element of output to 1.
  3. Use a counter initialized to 1 to iterate over the characters of the sequence.
  4. 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.
  5. If an 'I' is found, simply increment the counter and continue, as the array already has the numbers in increasing order from this operation.
  6. 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.

Comments

No comments yet.